Just put it in a ZIP file with AES-256 encryption. Upload that ZIP file to multiple locations, email it to yourself. If you're extra paranoid, you can also PGP-encrypt it.

If it's a large amount, do it on a cleanly installed Linux, and then secure-erase the partition after you're done.

Make sure your passwords are long and random.

Make sure you store your passwords securely.

Yes and yes. All wallet software that I know of has encryption. Or you can use a brainwallet that is never stored in a file at all (although you might want to keep a paper backup in case your brain has data loss).

> Or you can use a brainwallet that is never stored in a file at all

This is an incredibly bad idea. This publishes an unsalted, unhardened hash of your password to the blockchain to be cracked by anyone. There are bots with large precomputed tables that will instantly steal from especially weak ones.

You're right; I was thinking more of HD wallets where you don't choose the seed.

Https://strongcoin.com offers this service. The keys are encrypted on the client side before being stored on a server.