I'm on a very very tight budget as for now. I've started my own webhosting small business. I need to inform people about my services, is there any cheapest advertising method around?

Liteoff,

The cheapest thing I can think of that works is to walk around your community and join your chamber of commerce. Local people seem to always be looking to get online.

There were a few threads on this topic recently. If you go to the upper right hand side of the screen and click on search you can find some more info. Do a search for customers or getting customers.