In our experience if you are a small hosting company than nothing is better and cheap than doing local advertisement.
It might sounf funny but does your neighbour know that you provide a hosting service?
Start with that and you will see results much better than doing online expensive advertisement.
A local university students can be your potential customers etc...
We have tried that stratergy and have got good results.
Start participating in webmaster and web hosting forums with your site's link in your sig. I also agree with the Mrwonder, start locally as your local market can be a very good platform to start your business before you move on to a Global market.