Ignore the myriads of peple who are going to chime in below me with UBUNTU and ARMORY and etc etc etc. Well dont ignore them if you're highly technical.
The safest, easiest, and most effective cold storage is very simple: bitaddress.org
Wanna be extra safe, download their source files (link is on the home page) to a USB and run the webpage on a laptop that's never been online. Bip38 option. Pick a passphrase. Generate. Print (or write it down, but be careful). Bank Safe Deposit Box. Done.
-B-
Buy a Trezor. Write the seed down and store via Bitt's advice above.
I personally think that Trezor is too new and untested for it to be a reliable enough of a way to store large amounts of bitcoin, plus the fact that it has a high price will deter people from wanting to use it
Your best bet is to somehow generate a private key on a computer that has never been connected to the internet nor will be connected to the internet until the funds from the private key it generates has been transferred to another address