I think forums are a good place, they are the only place i have gone when i was getting hosting in the past.
You can normally tell what a host is like when you can see how they are on the forums, I can normally tell if someone seems to know a good bit, helps others (ie. will spend time to help a customer with any problems) and the like..
Its no way to judge a host at all but it gives you an idea i think.
Advertising in your local area is good, not too expensive.
Advertising on forums with a target audience is a great way to get customers, probably one of the best I think.