Getting your name into an industry as saturated as web hosting is a really difficult thing to do. Getting it out in a positive light is even harder.

You need to decide what your target audience is and then find a way to get a few large customers on board. Word usually spreads fast.

I remember my first hosting account was bought when I did a domainwhois on the forums I was frequently posting on.

AdWords is alright, but is very costly. I'm sure there are other (better) ways of doing it.

Purchasing an ad block on HD (or another hosting-related website) is probably a good way to start.

Hosting Discussion Advertising

Good luck!