I'd say it depends quite a bit on your target audience; who do you want your customers to be? I aim my hosting business towards the teens/early twenties personal website market, so therefore, I tend to advertise on sites/blogs/forums aimed at that demographic.

(Oh, and as for adwords, I think it's a bit of a waste of money, personally. I may try again at some point in the future. You do need to have highly targetted keywords in order to get any results)