Okay, i see a lot of replies that really don't make sense and don't help at all. Mocacinno's response was probably the best, although I think that he assumed that cold storage meant an airgapped PC, which isn't correct imo.
What I interpret cold storage as is any sort of storage device that is able to store your bitcoin private keys without an internet connection, thus having the maximum security. So paper wallets would be a subset of cold storage. Hardware wallets aren't really cold storage, even though they are really secure because whenever you plug it into a PC you are still connected to internet. Correct me if i'm wrong though because I do see people using both terms interchangeably.
I wouldn't recommend using a paper wallet, instead, look at Cryptosteel. They can cost quite a lot but i think it's worth it if you're storing for the long term. Completely offline and secure, immune to water and fire damage unlike paper wallets as well.