If you are using Authy, it backs up your keys on their servers - but this is less secure for obvious reasons.
For Google Authenticator, you need to back up the key when you set it up. Unless your phone is rooted, you have to make a backup of the QR code that you scan with your phone, or better yet, write down key provided along with the QR code. On a rooted device, you can simply back Google Authenticator up with Titanium Backup (just make sure to backup your Titanium Backup folder to a device other than your phone, and be sure to encrypt the backup since the authenticator secret keys are backed up in cleartext).plain