Cold storage is a term now thought of as the safest way to store coins.

To understand the safest way to store coins you have to understand how coins can be stolen. The private key is the key to the coins. Anyone who has access to the private key has access to the coins. This means if some company uses all paper wallets but is careless about who has access to them it's probably not safe, and this can't be thought of as 'cold storage'.

Cold storage generally means not only are the private keys not on a computer with any Internet exposure, but they are typically locked away too, like in a safe/safe deposit box. As long as the private keys are printed on some medium (or multiple mediums) which will not typically become unreadable, the coins they protect are then thought to be in cold storage.

Note: addresses can continue receiving coins while the private keys are safely locked away in cold storage.