I haven’t implemented this, so it’s possible I’m missing some details that change things. Lots of people are promoting it as a security improvement, but it seems like it could also introduce a weakness into account recovery.
Give Google your phone number, and when you want to log in they’ll send you a code by text message that you must use in addition to your password. So along with something you know – your password – access requires something you have – your phone. It seems like a decent idea, and would make it harder for someone to hijack your account. I might be reluctant to give Google my phone number, except they already have it if they look through my emails.
You can also list your phone as an account recovery option. If you forget your password, Google will send a temporary password to your phone that you can use to get into your account. This seems not so good. It sounds to me like someone could find or steal my phone, or even access it for a few minutes, and if they knew my email they could use the phone to get control of my Google account as well. I should probably keep my phone locked. But even so, the lock code can’t be as secure as my Google account password. So I’m reluctant to give Google a number for two-step verification, and then rely on them not to use it for account recovery.
Account recovery seems like a weak point. If I use two-step verification for logging in, two-step verification should also be required for account recovery.
UPDATE 1 December 2012: Dave Farquhar thinks about workable two-factor authentication; though it’s flawed, it’s about the best we’re going to get for now.