Your Apple ID is the key to many important things you do with Apple, such as purchasing from the iTunes and App Stores, keeping personal information up-to-date across your devices with iCloud, and locating, locking, or wiping your devices. Two-step verification is a feature you can use to keep your Apple ID as secure as possible.
If you no longer have access to one of your devices, go to My Apple ID to remove that device from your list of trusted devices as soon as possible so that it can no longer be used to help verify your identity.
Of note, it does not appear that two-step verification is needed to remote wipe or to access FileVault-encrypted files on a locked but powered-on Mac. It seems more likely that someone would get my Apple ID password than that I would need to remote wipe or would forget my Mac’s password, so I don’t have Find My iPhone or login password recovery enabled. I wish there were a way to enable Find My iPhone without enabling remote wipe.
Update (2013-03-21): Rui Carmo:
I am clearly in the minority that thinks of two-factor auth in and by itself as security voodoo to appease the unwashed masses — especially if you don’t follow it up with privilege separation — and I’m going to stick to my guns on this one.
I’d also like to note that if you have a non-phone, you don’t have SMS, and so in order to use two-factor authentication you must enable Find My iPhone and its remote wipe feature.
Unfortunately, today a new exploit has been discovered that affects all customers who haven’t yet enabled the new feature. It allows anyone with your email address and date of birth to reset your password — using Apple’s own tools.