There's a couple different ways of getting web hosting.
If you want to run a simple web server at home for some basic php/mysql development, then you can try
http://www.bizzarserver.com. However, hosting a server at home either over a dialup or even a cable modem can really degrade your bandwidth (to the internet) and will give your users a poor experience. Hosting at home is nice because speed isn't an issue for you, but normally, you'll want to upload it to a public server or web host once your ready. There's a bunch of different webservers for installing at home. Just google "wamp servers" which stands for Windows-Apache-Mysql-PHP and typically are bundled installs which are fairly easy to use.
Public hosting comes in a lot of different flavors. If your just looking for hosting, you can sign up with a shared hosting provider. Companies like this are dirt cheap but offer high speeds for your users for a couple dollars a month. Hosting is so cheap, just avoid the freebies unless you absolutely can't pay for one. A great company I've used in the past was
http://www.hostgator.com and they have everything from basic accounts up to heavy duty accounts. There's also a forum dedicated to webhosting talk at
http://www.webhostingtalk.com. It's a sister site to this site and there's a ton of shared hosting companies that are just itching for some customers. Shared hosts also provide you the opportunity to have something like cpanel or exim which give you added functionality to your hosting. You can install scripts, manage email accounts, and do all kinds of fun stuff. Just visit
www.cpanel.com to see what cpanel is about. Most are similar.
If your site explodes and becomes wildly popular, you can rent a whole web server. This typically will start to cost ya quite a bit a month. I've seen prices range from about $70-$150/month. Dedicated servers (as they are called) allow you shell access to install whatever you want. Very good bandwidth, upgradeable disk space, and a slew of other goodies. Very pricey, but if you outgrow shared hosting, then you'll need one.
The difference between having windows as a web server vs linux is pretty minimal with the exception of installing software. If your looking to just get started, I'd suggest just renting some space from a hostgator or some other shared hosting provider and work your way up. They are normally linux based, but I've seen a few be Windows servers. As far as writing php, it doesn't matter between the two since Php is pretty portable. But if you want to use asp, then you'll have to have Windows (installing asp support in linux is a pain) or if you want perl, Linux is usually a little easier. Mysql installs on both so that isn't really a big deal.
Hope this helps!!