What is the equivalent of cold storage or paper wallet for NXT?
It is possible, but quite more difficult than with Bitcoin.

All NXT tokens/coins are stored on the network, but it is possible to create an account "offline" that is secured by a 256-bit public key and does not expose your private key to the network.

There is a step-by-step tutorial on the NXT-Forum.