Well when i first started i was on a reseller for over a year and i mostly hosted clients from my design business. I then got a dedicated server and getting ready to get another and Recently i merged my design bussiness and hosting into one company Intrelix. I pay for some advertising and word of mouth works well, but to get word of mouth you have to be on top of your game and make customers happy. I have bartered some advertising mainly sponsoring sites that could bring in good amounts of related traffic. No matter how much money you spend on advertising you still have the chance to not get any sales. So to start go easy on the money spending on advertising. Try to get some local clients and start to build up a client base. Then start advertising a little more and soon enough if you made your clients happy with support and great uptime things will start rolling in. Just dont blow a ton of money off the bat. Keep some of it for emergencies.
just my 2 cents