The easiest and cheapest solution is to buy your domain hosting before you buy your domain name, for two reasons: most hosting firms will throw in a free domain name (so you won't have to buy it separately), and you won't have to deal with the mess often created (DNS records...) when ordering your hosting from a different company than your domain name (I've had cases where it took days and tons of phone calls).
As for web hosting: there are thousands of options available, as already pointed out. The AT&T hosting Broomiebar posted sounds ridiculously expensive to me... so does Copyright's for that matter :D
I use
eBoundHost for all my domains: for $9.95 a month, you get 3,000 GB transfer (compare to Copyright's 200GB), 300GB space (compare to Copyright's 5GB), 5,000 mailboxes (compared to Copyright's 500), and a free domain name. They have one for $6.95 a month, too (also with a free domain name).