Paper wallets that are properly generated offline and securely stored are immune to hacking/malware/etc. The idea is you never enter the private key into a networked computer until you're ready to spend the Bitcoin, and even then you can sign the transaction on the offline computer and transfer it to an online computer for transmission using software like Armory. The only way they could be compromised is by physically stealing the printed private key, or perhaps a weakness in the cryptography.

How paranoid are you?

If you're not very paranoid, you could use a web based generator like http://papercoin.org/ to generate a paper wallet. Ideally you should audit the JavaScript source code, use your browser's private browsing mode, and disconnect from the internet while generating and printing paper wallets.

If you're somewhat paranoid, you should boot a machine using a Linux live CD, generate the paper wallet, print it, and shutdown the machine, all while completely disconnected from the internet. See: Creating the ultimate Bitcoin Paper Wallet

If you're very paranoid you'd use an N-of-M scheme to generate M keys, any N of which could be used to recover the actual private key (e.x. 2-of-3, or 3-of-5), and you'd distribute the keys to M different safety deposit boxes

If you're extremely paranoid you'd destroy the computer and printer after generating your paper wallets. Or just compute your paper wallets by some rolling dice and performing the math by hand