How is the Gmail password stored in Android - and where? I have looked around and found no information on how Android manages to store passwords on the device. Especially Gmail passwords. I'm looking to learn how Android encrypts and stores passwords ? What key does it use and where is this key stored, and what encryption algorithm it uses.
Gmail's official app doesn't store password in your device. Your password is 100% safe if you use this app.

This is how it works: The password is used by Google's authentication servers for the first time ONLY. After first successful authentication, an Auth Token is downloaded to device which is stored in accounts.db file as plain text. For all subsequent logins, this Auth Token is used, NOT your original password.
So, if your device is stolen, all anyone can get is Auth Token which becomes invalid once you change your password. So, you'll be in ultimate command.
For ultimate security, I'd recommend you to enable 2-Factor Authentication &amp; create Device Specific Password for your device. After losing device, all you need is to disable that device. You don't even need to change main password.

Note: These all aren't true if you use third-party email apps for Gmail viz. Stock Email app, K-9 Mail etc. IMAP or POP protocol needs original password to authenticate users everytime. So, plain password needs to be available to email app before sending it to server. So, most of email apps store passwords in plain text (hashing/encryption is useless because hashing/encryption key needs to be stored locally). In this case, I'd recommend you to enable 2-Factor Authentication &amp; create Device Specific Password for your device. After losing device, all you need is to disable that device.

Update:
Technically, its possible to store passwords locally in encrypted/hashed form without keeping encryption key/ hashing key in plain text locally. Thanks to @J.F.Sebastian for pointing it out.  Unfortunately, such implementation for Android isn't available yet.  Starting ICS, Android provides KeyChain API using which an app can store a password locally in secure form. Apps using KeyChain API are rare, but stock email app uses it (Thanks to @wawa for this info). So, your password will be safe with stock email app as long as your screen is locked. Remember, KeyChain isn't safe if device is rooted and its not available on pre-ICS devices.