As far as I know's Google's authenticator app works by using a PRNG being seeded with a unique code for your account that's transferred when you first setup the authenticator and the current time. The app certainly works without a network connection.

AS for theft, you have backup codes which you should store securely (in a Truecrypt file with multiple backups or something), which allow you to log into your account once per code.