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.

Err, how can you do this if you need to go online to bitwallet to get the wallet generator? I thought you'd have to go to that website, then unplug the internet and get your bitwallet from a javascript on your computer, right? I'm not very tech savvy. Please explain. Thanks.