I know I can backup the contents of Google Authenticator on iOS if I perform iTunes backups with the "Encrypt backup" option checked. I'd wager that many who are backing up their phones don't have this checked, and don't realize if they have to restore their phone that the gAuth app will pretend you just installed it from scratch with no codes.

I'm not sure what the backup situation is with Android.

I've started backing up the actual strings that the app uses to generate the codes in an encrypted vault. You usually have to manually have these strings shown to you in lieu of a QR code. While creating another avenue for someone to hack you, at least I have a backup as well as a way to add a second device go show me codes. This is definitely beyond the capacity of the average user.

I think there might be online services that handle keeping codes for you? Like you can install an app on your phone, log into an account, and it presents you with all of your codes. Anyone have a recommendation for one of these that works well for them?