Here's how I create my paper wallets...
1. Get a fresh new USB. One you know doesn't have any malware on it. You can also use a CD. You know, one of those old things that played music back in the day.
2. Download Ubuntu onto the USB/Cd from
http://www.ubuntu.com/download/desktop
*note you will also need software to create a liveUSB. I use LiLi.
http://www.linuxliveusb.com/3. Download
Bitaddress.org into the USB
4. Shut down and boot up with the live USB. (press F12, choose USB.
5. Click try Ubuntu.
6. Open a Firefox private browser (right-click Firefox)
7. Go to file:///
8. Click cdrom
9. Open bitaddress and create a paper wallet. Use BIP38 encryption if you so choose.
10. Print it. Keep it safe.
Once you've done it a couple times it's very easy and straightforward.
I also have these steps if you want the same security but you need a vanity wallet such as 1Chris4GEoLLjdh4juFXGwY7snaazuxvKb
1. Go on bitaddress.org offline, on a Ubuntu live USB
2. Generate as many single addresses as you want
3. Convert Pub key to Hex (wallet details on bitaddress.org)
4. Make a list of hex addresses + private keys and print it out (don't save it on USB. That's going to run on Windows again)
5. Boot up windows
6. Start > Run > Cmd
7. Drag over vanitygen64 to cmd (enter) drag over vanity address again (space) -v -P (hex pub key) 1xxx (whatever you want as your vanity) (enter)
8. Copy partial key down on USB
It will now generate your partial private key
9. Shut down windows - Boot up Ubuntu Live USB
10. Open bitaddress again and go to vanity address and put in the private key (from step 4) and the partial private key. This should give you the vanity address that was calculated on vanitygen.
11. Print out the wallet details page (to have the QR codes)
12. Import the public address into mycelium or your wallet of choice.
Optional: Import the private key. If you don't it's a paper wallet, if you do it's a hot wallet.
It's a little daunting trying to do the vanity paper wallet address. I'd work my way up to that if I were you.
Good luck!
EDIT: I have an old 'dumb' printer that can't connect to wifi and has no internal memory. I would only suggest using these or you just wasted your time haha.