The way Bitcoin is designed you only really need a private key to store them. Technically you don't even need a computer. Your private key is a long string of characters which allows the bitcoins to be sent elsewhere. Some people print private keys out for safe keeping and others package them into physical coins.
Most people, however, want the ability to send bitcoins at anytime too. For that you need to pick from available software options.
The first thing to understand about storing bitcoins safely is the private key is the key to the bitcoins. If someone learns your private key they can steal your bitcoins by sending them to their own address. If you lose your private key you lose the ability to send those bitcoins forever.
With that in mind let's discuss common storage options.
To send and receive coins easily you'll need a "wallet" which generates bitcoin addresses, the public addresses you give for people to send you coins. You can either install wallet software on your own computer or use an online service. When using any online service, even the most reputable, keep in mind you're trusting that they protect your coins. For any significant amounts you probably want to securely store bitcoins yourself.
The best online wallet to use is probably Blockchain.info. Not only is the owner a reputable member of the Bitcoin community, the way the site works he never knows your private keys. Assuming the owner is trustworthy, losing coins would probably only happen if his server was compromised. However, that's still something to consider.
Alternatively, to install wallet software on your own computer you probably want to use MultiBit. This is known as a lightweight client, allowing you to send and receive bitcoins on the network without downloading the full block chain. When installing any wallet software on your computer remember two important things. If someone gains access to your computer either physically or using viruses they might learn your private keys and steal coins. Second, if your computer crashes, which can happen anytime, you might lose access to the coins forever. So you need to protect against these two things.
The best way to protect against unauthorized users on your computer is to encrypt your wallet file with a strong password only you know. That way if someone gains access to the wallet file they won't be able to read it. However, you need to protect your password so you don't lose it too. To protect against computer crashes you should back up your wallet file in at least 2 different places. The nice thing is your wallet file is simply a file like any other file. You can save it many ways, and if it's encrypted you don't have to worry about anyone accessing it. You should also refresh your backups before reaching 100 new addresses. More information is here: https://en.bitcoin.it/wiki/Securing_your_wallet.
For anyone who wants to store a large amount of coins in a way almost guaranteed secure against any problems the best route may be using Armory. Simply visit that site and follow the straightforward steps to secure bitcoins.