there are many ways to promote a website. one of course as some body mentioned adwords or publisher. another is called SEO/SEM "search engine optimization" or search engine marketing if you're living in UK. what the heck is SEO or SEM. It is a method to help you to rank your site higher naturally in major search engines such as google or yahoo. Well, generally SEO is expensive but imagine adwords, in hosting indusries, at least $4-$5 a click. if $100 can only gets you 20 click. So I definitely thinks SEO is the way to go. Like my website, 18AffordableWebHosting.com, I've got about a week to listed in google but generally it may takes 10 weeks in the process. what i did was some SEO methods or techniques. therefore if you guys need to know more. I've got a great ebook about SEO written by some top internet marketer Brad Callen and certainly it costs some money and it generally tells you how to rank a website higher in search engines.
From my experience the easiest way to advertise a hosting service is from forums and other websites. If you commonly post on large forums and show what you can provide people are much more likely to sign up. Just getting your name out is a good start, and as you get more customers it is likely that they will draw even more people. Getting those first few people is crucial, and also happens to be the most difficult part.
There are so many option for advertising but which one is the right one? The answer is there is no right one. Its a game of trial and error to get the best results. While banner ads might work great for one company it might not for the next.
In my opinion there is only one advertising method that is full proof and that is word of mouth. Now that is if you have a good reputation. Word of mouth is free and if you got your customers commenting your service to others it is priceless. But remember it can also work the other way around and that can be the killing point of a company.
I have used everything from adwords, banners, affiliate program, and forum posting. I found that it depends on many factors on what is going to work best for you. We use many different methods of the above and sometimes the return is good, other times it is not. It will always be an ongoing strategy that you will have to adjust on and on.