Peter: When you use certain mobile apps (take Evernote for example), you don't get redirected to the website to grant permission to the app. Instead, you just log in with your username and password, straight inside the app.
Actually Evernote uses OAuth. OAuth2 allows different authentication workflows. The Resource Owner Password Credentials Grant does not open a website.
Peter: So, I'm wondering how this works, and where to look to implement this. Is the password stored on the device, and sent to the website?
An Android Authenticator is able to store an authentication token as well as a password on the device. The Authenticator will use the authentication token - if available - to access your web application. If no token is available, it will try to get one with the password, which will be retrieved through a login dialog. Therefore you could avoid storing the password, but as soon as the authentication token expires the login dialog will show up. Also Google recommends avoiding to ask for passwords when possible:
In general, we recommend minimizing the frequency of asking for user credentials—to make phishing attacks more conspicuous, and less likely to be successful. Instead use an authorization token and refresh it.
Peter: Is this actually safe?
You may assume passwords are stored securely. Put simply, Android works like a Linux system, where every app is run by another user, so that apps cannot access each other without public APIs. Note, that a rooted Android phone weakens that mechanism.
If you want to skip implementing OAuth, you could create a more simple login service, which returns an authentication token (for example a session id), but as always when rolling out your on security system, there are many pitfalls. Therefore I advice you to look for an OAuth framework (for example Apache Oltu) and implement an Android authenticator the standard way.