With a shared server you share the server with other people. How many other people you share it with depends on the host. Some servers will hold a couple of thousand sites quite happily and some will only hold tens of sites. It depends on the server specification and the type of sites that are being hosted. You can expect to pay between £0 and £15 per month. You get what you pay for. For a small site you should be looking at shared hosting and to spend around £2 - £8 per month...
If you have a dedicated server you are the only user on that server. It means you know that the server won't be overloaded unless you do it yourself. You can either have an unmanaged server (you do it yourself) or a managed server (your host does it for you). Expect to pay £50 - £500 per month in most cases.
You provide your own server and rent rack space and transfer. Expect to pay upwards of £50 per month (and hundred or thousands of pounds for the server up front).
Linux and Windows
Don't worry about Windows being less secure than Linux. If your host is competent the server will be kept up to date and you shouldn't have to worry about being hacked - the same goes for Linux systems. Choose what's right for you and your plans. If you want to program with PHP and MySQL you'd be far better off with a Linux system. If you want to use .NET, ASP or MS Access you'll be much better off with a Windows based system.
This is how much hard disk space you are allowed to use on the server. The average web page is about 40 kilo bytes so most people only use a few mega bytes of space.
This is how much data is allowed to be transfered to and from your site. Assuming each page is 40KB, a transfer allowance of 1GB will give you 26,000 page views. Of course, if you're letting people download files or have a lot of images this won't apply. If you are using a lot more bandwidth (20 to 100GB or more), it can also be expressed in terms of "512 Kbps" or "0.5 Mbps" rather than Gigabytes per month--They are different ways of measuring bandwidth. An "average" of 512 Kbps" would be about 162GB/month.
If you're being offered unlimited bandwidth or transfer stop to work out how they are doing it. Do you have an infinitely large hard disk or infinite fast Internet connection? No? Neither does your host. They're over-selling. It's a short business model that has one ending.
The location of your host/server is something else that you should consider. A host located in the Far East is probably not ideal if your site has a UK based audience. Physical distance is not the key, but network topology is. If you're hosting a small personal website, then it doesn't necessarily make any difference if it's hosted in the U.S. You should also consider latency (the time it takes for your packet to go to the remote site and come back) which is slightly more critical on physical distance due to the speed at which light travels in fibre-optic cables. If you are looking to host a commercial website, then you would generally (although not always) be better in the U.K. Similarly, it ensures your content is hosted under U.K. law (unless your aim is to go around UK law--but talk to a lawyer first )
You can 'trace' the route that packets would take on many websites. You can find a list here.
(MFN use airport/country codes in the reverse DNS records that you see when you run a traceroute - you can usually work out where the server is from that. Go here to trace from MFN's network)
Broadly speaking in the current climate, download speeds should be the same in the well connected countries but things may feel slightly sluggish.
Find out who you're dealing with
Are you entering into a contract with a registered company or a sole trader? Or, worse, don't you know? Your host should give the relevant legal information on their site. If the host is registered you can check their details free of charge at Companies House. If your host goes under you should make sure you know where you stand (chasing after "the bloke who ran it" or "a-very-good-host.com" won't get you your money or domain name back - you need names and addresses)... There some useful lookup tools here.
It may be in your interest to register your domain with a third party - i.e. not your host. If your host goes under you will be able to change hosts far more easily than if you're relying on a defunct company to authorise the transfer.
If you need to add users, set up email forwarding, etc you'll need to do it through your host. Most hosts have a control panel to do this. If the way this control panel looks and feels is important to you you may want to ask for a demonstration first.
PHP, MySQL, ASP, CGI, SSI, etc
If you need server side scripting you must make sure your host supports it. Most sites now use some form of server side scripting so it's fairly standard but not everyone offers it. If you're unsure PHP and MySQL are a safe bet unless you have other, more specific, requirements. If you want a forum/bulletin board system on your web site you'll probably need a database like MySQL or MS Access and a scripting language like PHP or ASP.
Be very careful when being asked to pay a year up front. You may change your mind and decide that you don't want your web site anymore, that your host is [censored] and unworthy of your custom or they go under and you never get your money back. Try to pay monthly or quarterly. If possible, use your credit card but if you're only paying monthly or quarterly you have far less to loose than someone whose paid 12 or even 24 months up front.
By law your host is required to show an address on their website. If they don't have one look elsewhere. You may also want to whois your host's domain name to see if anything interesting turns up.
Ask around, but beware of newbies/anonymous posters and people making you click refer-a-friend links...
Big thanks to eden for writing most of the above