When discussing bitcoins, cold storage generally means secure storage that cannot be accessed from the internet, and for which spending requires manual intervention by the human being (or group of human beings) that are intended to have access.
When properly created, a paper wallet can be a "cold wallet", but if it was created online, or contains private keys that have ever been accessible online, then there is potential that someone other than the intended human being (or group of human beings) has (have) access.