I offer my standard advice:
1. Establish your requirements, i.e., Linux, Apache 2.4+, PHP 5.2+, MySQL 5+, the preferred control panel (e.g., cPanel) and storage and bandwidth requirements. Remember to allocate for log files, databases, e-mail (attachments) and growth.
2. If you're looking for a VPS or dedicated server, remember to ask what the host's managed services provide. Remember, a non-managed host must be monitored by you 24/7/365!
3. Know what control panels you are willing to use, i.e., WHM/cPanel. cPanel is the standard bearer for Linux systems and Plesk for Windows systems.
4. Know how much CPU time/RAM you need. If you need a lot of processing power (like Zoomla and other CMS's), this will be a major factor. These, however, are usually specified only for VPS/dedicated accounts and automatically throttled for shared/reseller accounts.
5. Know your target (the Internet is fast but some latency could hurt so the closer your server to your target audience the better) location and try to host as close to your target as possible.
6. SEARCH (using the above parameters) recording each feasible host as well how well it satisfies your requirements and budget. Spreadsheets are good for this as you can assign weighting to the different requirements and how well they were met to generate numerical scores.
7. Create a shortlist based on the database you've created in step 5 then SEARCH for comments about the host (avoiding obvious shills and websites which advertise for that host).
8. (from EastCoast) "Eliminate anonymous companies - if a hosting company doesn't have a full office address and company registration details visible on their site, it's often down to the amateur status of the operator, which is unlikely to be consistent with longevity and reliability."
9. (from EastCoast) "Eliminate new companies - hosting has a very high fail rate because of the low barriers to entry. If a company makes it through it's first 5 years then it's likely it's jumped a few hurdles and knows what it's doing sufficiently to have made a viable business. Not all new companies are cowboys, but the percentage is high enough that it's not worth the risk of being the one to find out the hard way, when there are plenty other options."
10. Eliminate companies which do not tell you exactly what you're getting for your money, i.e., the Control Panel, the storage, the bandwidth (traffic), the versions of the main daemons (Apache, PHP and MySQL), the SSL and dedicated IP charges, etc. That's where knowing your requirements comes in strongly!
11. The last step (other than selection) is to contact each shortlisted host with a question (I've used .htaccess and mod_rewrite availability, which services are managed by the host, the availability of IP addresses - you will require one for each SSL you use - or ask to test proprietary control panels - they may make life too difficult for you) and record the response time and your level of satisfaction with the response.
12. Finally, you'll have enough information to make an intelligent selection: "Just Do It!"
Been there, done that (all too frequently in the past).