What matters is that your private key(s) shouldn't connect to the internet, so your wallet is secure and protected against hackers.
Paper wallet is recommended because your keys are on a paper and there is no way for a hacker to access your paper. Take note that if you don't generate your paper wallet properly, it wouldn't provide the security it should. For example, if you generate your paper wallet using an unsafe tool, it's possible that all your fund is stolen. Or if you generate your keys on an online computer, it wouldn't be a cold storage and wouldn't have a big difference with an online wallet.