As a platform, Magento is at an enterprise level, meaning it is easily capable of handling from a small online store, with 10-20 products to a large shopping portal with thousands of items, lots of visitors and a high volume of orders. 

Because of this, it is hard to write up a checklist of what a good hosting solution is for your needs. I will, on the other hand, try to look at some key elements and make some recommendations along with the rationale, giving you a guideline on how to choose a good server for you.

Server Models

There are two types of hosting services you will find available pretty much from any major seller on the web: shared hosting and dedicated hosting.

Shared Hosting

The term shared comes from the fact that none of the hardware resources such as processor, disk drive or RAM are allocated to you alone. This means that your server's performance is going to depend on how much traffic and resources you and your "neighbors" are using. 

Apart from the hardware, you are also sharing the same operating system with other users, thus limiting your ability to make core changes to your server's environment. For instance, Magento requires some PHP libraries that usually do not ship with standard package; today most shared accounts I've worked with do provide all necessary libraries, fortunately, but in the off chance they don't you might end up needing to ask your provider to install them, something they might not be able to do in order to not break anyone else's setup within the same machine. 

One of the major advantages of shared hosting is the price; starting anywhere from $3/mo, it is cost effective. 

Recommendation: Unless you plan on having more than 100 or so products and not counting on a large amount of visitors (though I do hope you get as many as possible) than Magento will work satisfactory on a shared hosting account. 

Dedicated Hosting

As opposed to shared hosting, dedicated hosting means that there are hardware resources allocated to you, and you alone. By today's standards, processors are so fast that they are no longer an issue for large vendors, leaving you with dedicated RAM and storage disk size. 

Because you get dedicated hardware, it's as if you get your own machine with your own operating system which you can manipulate and customize as much as you want.

The advantages of such a solution is performance and flexibility. It is worth every penny of the larger price tag on it, starting at around $30/mo.

Recommendation: If you have a larger product database and a high volume of daily visitors, you should definitely look at getting a dedicated server solution.

Individual Components

Operating System

Magento is built to work on a Linux platform regardless of the flavor. Most shared servers come with a Fedora OS; if you choose a dedicated solution, go for a CentOS flavor Linux because it is an enterprise level OS and it will match your enterprise level platform, Magento.

PHP and MySQL

Most shared hosting vendors will offer a somewhat latest version of both software. They need to keep up to date because of security patches and enhancements, so I wouldn't worry to much about it, but you will need PHP version 5.3 or higher and MySQL 5.0.2 or later.

If you get a dedicated server, usually they come with a bare OS, so you will have to manually install both software on it.

Disk Size

Unlike a few years ago, storage disk space is such a luxury, most shared accounts having virtually unlimited storage space, and dedicated servers having a minimum of 20GB, which should be plenty for any size store. 

RAM

Shared accounts do not have a certain amount of memory allocated, so you will have to make do with whatever is available. For dedicated servers and larger stores, a good rule of thumb on choosing memory size is the daily visitor count: you should have 1GB of RAM for each 2500 daily visitors. Also make sure you have at least 512MB available for OS processes and MySQL queries. - I recommend a minimum 2GB of RAM.

Server Compatibility Tool

Magento offers a little PHP file which acts as a checklist that runs a diagnostic of your system and tells you if Magento will work or not. You can download this tool here and all you need to do is upload the extracted magento-check.php file to your server's root folder and run it by accessing http://example.com/magento-check.php (replacing example.com with your domain name). It should output something like this:

Conclusion

I have set up Magento on both types of server and I've had positive experiences with both, but I strongly recommend that you spend the extra money on a dedicated server, with 2GB RAM and a CentOS operating system for a general purpose smooth running Magento Store.

I hope this helps you make a more informed decision. Let me know in the comments below if you need anything cleared up further.