The basic concept of "cold storage" or a "cold wallet" is to store your Bitcoin offline. This means that there is no direct network connection that could possibly lead to your Bitcoin wallet being compromised.
Paper wallets are physical Bitcoin that you print out. They contain your Bitcoins' private and public keys. Once Bitcoin is transferred to a paper wallet, it can only be put into digital form by presenting the private and public keys that are printed on the paper wallet. This makes paper wallets a very popular method of doing cold storage. Paper wallets should always be stored in a secure location. If a paper wallet is lost or stolen, the Bitcoin stored on it cannot be retrieved.
A brain wallet is less popular but can be very secure. To create a brain wallet a user must create a phrase that has a very high level of entropy (uncertainty). Once this phrase is memorized, a cryptographically secure hash such as SHA-256 is created of that phrase. This hashed value is used to generate a Bitcoin address and it is also used as the private key for that address. This method allows you to store the private key offline (in your brain) and is much more secure than storing the private key digitally. If a brain wallet phrase is forgotten or the individual(s) who know it are no longer alive, the Bitcoin in that address will not be retrievable.
Another popular way of doing cold storage is to store a Bitcoin wallet on a offline storage device such as a USB drive, SD Card, etc... When storing a wallet on one of these devices, it should be encrypted and protected by a secure password. The password should be at least 20 characters in length and contain upper case letters, lower case letters, digits, and special characters. An example of a good password is: C|X6+aV/@*n8CD5.=Y+#oar%s. This password should NOT be used for any other purpose. The security of this method is dependent on two factors:
In the event the password is lost or forgotten or the device is lost or stolen, the Bitcoin stored on the wallet is not retrievable.