Reliability, support, speed, and price.
I've gone through a number of hosts, and finally found the right guys a few years back.. Their uptime is great, their support is incredible (all done online, but responses are usually within 30-60 minutes, even at 9pm at night), their speed is awesome, and their price is competative.
eMax Hosting
There will always be cheaper guys out there, but you do get what you pay for. I use a cheap host for some of my recreational sites (How can you argue with 1-year hosting and a free domain name for $15 for the year?!), but for my e-commerce sites, I don't mess around - Any downtime can cost me WAY more than my monthly hosting costs.