Contributing to forums like webhostingtalk and sitepoint are really great for starting out. The owner of my old webhost posted on those forums frequently, and while his services weren't very stellar (IMHO), people kept flocking to his hosting company, because he was very respectable and helpful on these forums. Never mentioned about his company directly (just in advertising forum and through his signature) either.