Breaking into the web hosting business is hard, especially with the market being as saturated as it is. My company has yet to use things like Google AdSense, but we started out as a Game Server hosting company and eventually added on VPS hosting. The kinds of advertising we've done has been mainly forum posting and word of mouth. As a game server provider, getting involved with sponsoring events and servers (which cost practically nothing to do) for events is a good way to promote our other services as well.