Android - How is the Gmail password stored in Android - and where?
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 & 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 & 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.
Android passwords used with the built-in Email application are stored in plain text inside a SQLite Database. This is in contrast to the Gmail application, which uses Auth Tokens as described in Sachin Sekhar's answer.
For Jelly Bean, the database location is:
/data/system/users/0/accounts.db
The above location varies with the Android version
This location on a non-rooted device is secured and protected by the Operating System.
On rooted devices, users have already technically cracked their own security, and even if it wasn't in plain text it would still be trivial to decrypt as the key has to exist somewhere on the device to do it.
A member from the Android Development Team posted an explanation that till today still applies:
Now, with respect to this particular concern. The first thing to clarify is that the Email app supports four protocols - POP3, IMAP, SMTP, and Exchange ActiveSync - and with very few, very limited exceptions, all of these are older protocols which require that the client present the password to the server on every connection. These protocols require us to retain the password for as long as you wish to use the account on the device. Newer protocols don't do this - this is why some of the articles have been contrasting with Gmail, for example. Newer protocols allow the client to use the password one time to generate a token, save the token, and discard the password.
I urge you to review the article linked to in comment #38, which is well-written and quite informative. It provides some very good background on the difference between "obscuring" passwords, and making them truly "secure". Simply obscuring your password (e.g. base64) or encrypting it with a key stored elsewhere will not make your password or your data more secure. An attacker will still be able to retrieve it.
(In particular, some claims have been made about some of the other email clients not storing the password in cleartext. Even where this is true, it does not indicate that the password is more secure. A simple test: if you can boot up the device and it will begin receiving email on your configured accounts, then the passwords are not truly secure. They are either obfuscated, or encrypted with another key stored somewhere else.)
Aditionally, since this issue appears to disturb many Android users, you can also follow this discussion at Slashdot - Android Password Data Stored In Plain Text.