If each app on Android gets its own UID, then how are phone users identifed? Do they own some different UID or something? Or are they in special group "users"?
The human users of the phone don't correspond to different Linux users. The human users are identified only within Android itself, not to apps. Android provides a completely separate environment to the app for each user - a little like a Linux
chroot - so the app doesn't have to worry about separate users. When a new user runs the app, it just looks like a fresh install on a new device, because it's given a brand new data directory, separate from those it's given for other users.