Try to create something that is more valuable than your competition. Either go cheaper (difficult, in the shared hosting biz.) or provide some service above and beyond your competitors (I know of many successful hosting companies that targeted a certain kind of customer, for example, real-estate agents during the boom, and basically sold nice templates for their niche.)
Another thing I notice is that if you post good technical info about what you are doing, you get good links (and thus pagerank.) You need documentation anyhow, so cleaning it up and posting it online is like free advertising.
But what do I know. it's not like my hosting company is wildly successful, and I had what was once a unique product, Xen VPS hosting (I started before ec2, using Xen2 on NetBSD. Of course, I now have a whole lot of competition, and I don't have the cool provisioning systems they do.) and I still have a almost 2x price advantage over my nearest competitor. My biggest problem is credibility. I need to dedicate a weekend to web design, as my current website is inconsistent and out of date. (I have some technical issues, too... but after last weekend, I've cleaned most of those up. I will be writing up a thing on puppet this coming weekend. So embarrassing. I was aware of the problem, and policy was to fix it on all new servers, I just forgot to edit the config files in question. Yeah. moving to puppet.)
Still, my company is growing about as fast as I can get new infrastructure up (which isn't as fast as you'd think. I've got two other essentially full-time jobs.)