The most common approach seems to be backing up your (encrypted) wallet on cloud hosting services such as Dropbox and Google Drive. To reduce the risk of theft, use a very strong password to encrypt your wallet, and do not store the password anywhere less secure than the password itself (e.g. if you use a password manager, it should also have a very strong password).
To reduce the risk of accidental loss, keep backups in multiple places. E.g. Dropbox, Google Drive, email it to your family and friends, back it up to an external hard drive; if one of these disappears, chances are still good that you can recover it from another source. You don't want the keys to be in only one physical location...e.g. having the only backup be in your house means that a house fire or theft could mean you lose your bitcoins.
Just don't forget the password! Maybe you should write it down and keep it in a safe deposit box at a bank, and/or keep paper wallets there, if it's worth the cost to you (maybe $15/year for a small box).
A rather different approach is taken by deterministic wallets like Armory and Electrum, which generate one root key or seed and then generate your private keys and addresses from that. Armory's root key works on the idea that you print out the ~256-bit root key in one or more fragments, and need the appropriate paper records to restore your wallet. Electrum's seed is a 128-bit number represented by 12 common words, which you commit to memory and/or write down. Securing these records would follow similar guidelines to a written password or paper wallets.