Hosting options
Dan says he usually uses 1and1.com for hosting. It's $5.99 per year to register a domain and web hosting starts at $3.99 per month. Gary says check out rackspace.
Rackspace
Rackspace comes with the following installed on Linux servers: Apache 2, BIND, GCC, OpenSSH, OpenSSL, Perl, PHP, MySQL, Python, Sendmail and Postfix (enables), Webmin. Their pricing is not disclosed on their main web site, but from browsing around it is "expensive" (hundreds per month for the server), but you get your money's worth. But it seems like too much to start off with - maybe later when we have a large client base?
1and1
1and1.com can provide a Fedora Core 4 linux server for $99. You get 2TB (2000GB) of transfer per month, I can't imagine we'd exceed that! It says I have root access, I need to determine if I can dump all the stuff I'd like to up to the server. Note that the cheaper "we'll host your web site" options only include a predetermined set of software tools.
Needs further research...