Securing your bitcoins in offline storage

There are various levels of security that you can apply to your bitcoins. A specific level of security should be applied depending on the size of the stash.
A mobile or online wallet is often sufficient for smaller sums that you intend to be using for online trading or online purchases. I would still recommend enabling 2 factor authentication for any online wallets and avoiding rooting or jailbreaking your mobile when using mobile wallet.
However the ultimate security for your bitcoins is a wallet that is completely disconnected from the internet and as such unreachable by hackers.
Such wallets are commonly called offline wallets or cold storage and some concrete examples are paper wallets, other physical media, USB hard drives and upcoming dedicated hardware devices.
I’d like to talk about encrypted paper wallets because they appeal to me the most as a cold storage due to their simplicity and the low cost of creating them.
The common theme when creating offline wallets is that any device used to create them has to be offline and the wallet itself can never be connected to an online device until you plan to spend the bitcoins it contains.
An offline wallet will prevent any money to be spent but you are still able to send bitcoins to it and to view the balance easily. Just import the public key into your favourite wallet client.
(Remember that a bitcoin wallet consists of two parts: the public key is like an account number that you give out for people to send money to and you can also use to check the balance. The private key is like a PIN code that is used to spend the bitcoins. If anyone finds your private key your wallet will be emptied and this is irreversible).
When combined with the very strong encryption standard BIP0038, the paper wallet can even be publicly shared without risk of being compromised (as long as the password is kept secret). They can also be packed up online!
What you need: a live linux cd, source code for bitadress.com, one or more usb drives, a printer.

• Download the bitaddress.org code to your freshly formatted USB stick
• Download Tails linux ISO and burn it to a DVD.
• Boot up your computer using the DVD and load up bitaddress.org html from the USB stick.
• Generate one or more encrypted paper wallets and scan the public address so that you can send coins to it later.
• Save the paper wallets as PDF to the USB stick(s)
• Print multiple copies of the paper wallets or write down the private key manually using pen/paper.
• You are done

If you find creating and booting from the DVD complicated you can use the online versions of bitaddress.org but be aware that your are then exposed to any man-in-the-middle attacks or if your computer has been compromised an attacker could get hold of all your paper wallets.
Additional steps depend on the sum you are planning to store. Put the paper wallets in waterproof bags. Leave a copy with a friend you can trust. Consider storing a copy in a safe. Split up your stash between multiple wallets to lower the risk and to allow for spending in increments.
A recent version of the Android mobile wallet Mycelium has added import of BIP0038 encrypted private keys. This makes it very easy to scan the encrypted wallet and start spending the bitcoins on it.