[Matt_Cutts]

What evan_ said: you're using the phone as a pocket computer, not as a phone. You don't need phone service at all--the authentication program will run on your phone even if you don't have service or you're in a foreign country.

Enough people have asked these (very reasonable) questions that maybe I should do a video about two-factor authentication.

[stumm]

This video made by Google is pretty good and covers many of the concerns people have: http://www.youtube.com/watch?v=zMabEyrtPRg

[Matt_Cutts]

Nice--you're right, that video covers pretty much everything!