Good question.
First thing you need to do is try to evaluate what your needs are in terms of space, bandwidth, and OS. For most people a Linux based host running Apache will serve their needs. If you want to run .ASP or .NET you really need a Windows based system, but these tend to cost more for.
There are many, many, many hosting providers out there, be careful, many stink to high heaven. Avoid "deals" that show up on e-bay, you'll more than likely get burnt big time. Avoid hosts that offer "unlimited space" and or "unlimited bandwidth" there aint no such thing. Be careful during summer vacation time, lots of "kiddie" hosts suddenly spring up and disappear again when school starts up.
Test out a hosts support before commiting to them, do they offer phone support?, trouble tickets?, email?, AIM etc. ? Are they in a data center with reliable power and backbone connections?
Before you make a final decision on a host I would do two things. One go to a site like webhostingtalk.com and do a search on the company to see if there are any horror stories you need to be concerned with.
I currently use micfo.com, reasonably priced and great support. They allow multiple domains on a single account, so I currently have hipower-rocketry.com, rocketlist.com, nerrf.com, nettechjedi.com, and a friends table200.com sites all on the one account.
Prior to micfo.com I used ipowerweb, but their support stank. Prior to that I hosted on my own server, but my bandwidth was limited and it would have cost more per month to increase the speed of my connection than it cost to host elsewhere.