I think the idea of cold storage is that the private key never touches the internet. You create the public/private key pair offline, save the resulting address, then move that online. The private key should never be on a computer that is online. And best practice is that the computer that created the private key NEVER touches the internet after that.
Pente is correct, the idea of cold storage is to make the "wallet" on a cold computer which is a computer that has never been connected to the internet and will never be connected. that is why a live Linux is a common OS to use in situations like this. and you can simply do this with their wallets, your download the code, run it offline to generate keys and save the wallet.dat file.
and then if that altcoin is similar to bitcoin meaning the only thing you need is a private key, then you print that private key on piece of paper and you have a paper wallet.
majority of altcoins are like this, some of them are a bit different, you need to look them up yourself and check to see if it is going to work or not. I never hold altcoins for long to know this!
one problem you may experience is the lack of tools to broadcast your transaction. with bitcoin you can simply make the transaction (unsigned) online and then transfer it to your offline storage and sign it there. many altcoins don't even have this feature. then after signing you need to come back online and broadcast, again you either have to be running a full node yourself or use a tool to push (there are no tools to push altcoin tx online)
Thanks for the responses Pente and Pursuer! Very Helpful!
Some follow up questions:
1. So do you need to buy an entirely new cheap computer to properly do cold storage, and then basically never use it again?
2. I've never heard of live lunix, why is it commonly used in these situations?
3. You still need to get the "wallet" onto the computer though, right? So you would download the wallet on a computer that is connected to the internet, then transfer it to the non-internet computer via usb stick?
4. Pursuer, what do you mean by "you can simply do this with their wallets,"- who is they?
5. Is there a difference between cold storage and paper storage? I was thinking that storage was always best on paper, and that the non-internet computer was just a step to do that.
6. Hmm.... so it seems like the tools aren't developed yet for most altcoins to do really proper safe paper/cold storage (unless you have alot of tools/resources/knowledge yourself). Is this a fair assessment?