Electrum is great and perfectly suitable for cold storage. Not only can you back up an encrypted copy of the wallet and take it offline, but you also have additional safety, since you can keep a copy of your seed written down on paper in a safe place (perhaps a safety deposit box, or buried in your back yard ). Paper wallets are okay, too, but you need to be very careful to plan for contingencies if one copy gets destroyed. Consider laminating them and keeping multiple copies if you go that route.

As some have mentioned, hardware wallets are really cool. I've heard great things about the Trezor and Ledger Nano but I don't have experience with them. I'm also worried about long term data integrity and I'm not sure how their backups work. I use Electrum for my cold storage, personally. Good luck!