The easiest way to generate a paper wallet IMO is to use bitaddress in offline mode.
You could completely format your harddisk before and after generating your paper wallet for extra security.
It would be the safest to boot Linux from LiveCD and generate your wallet there. If possible, an computer that have never and will never access the internet. You could completely format your harddisk before and after generating your paper wallet for extra security.