How to generate a paper wallet?
If you follow the procedure at How to download bitaddress.org to use offline? for creating a paper wallet on an offline / airgapped computer, you can be fairly certain that your private key will not be compromised during the process.  For more info, see https://en.bitcoin.it/wiki/How_to_set_up_a_secure_offline_savings_wallet