Word of mouth works the best, I've been around for near 4 years at various places within the hosting industry, and I've allways used word of mouth. It works the best.
However, it is slow going to start and you have to work a bit harder to get those first 30 customers or so, but past that point if you treat the customers right then you'll start to pickup business and you'll be growing. But again, it will take a lot of time.
I guess advertising in other ways is ok and can be helpful to create a "buzz" about your company, but thats only half the battle, the other half is getting people to say that you indeed are a good company

.