Technically the server doesn't need to have a UID/GID database that's aligned with the client, what's required is that all clients of the same server are aligned. The server will take the numerical UID/GIDs from the RPC sent by the client and perform Posix style permission checks using the owner UID, owner GID, and mode bits stored in the inode of the file or directory. The server doesn't need to known what user the UID corresponds to.
This was maintained using YP/NIS. But Sun was too big for a single YP/NIS domain, so there was a hack where each YP/NIS master was populated via some kind of uber-master database. At least at one point, this consisted of plain text files on a filesystem that was NFS-mounted by every YP/NIS master....
This was all terribly insecure. Since everybody had root on their own workstations, you could `su root` and then `su somebody` to get processes running with their UID, and then you could read and write all their files over NFS. But remember, this was back in the day when we sent passwords around in the clear, we used insecure tools like telnet and ftp and BSD tools like rsh/rcp/rlogin. So NFS was "no more insecure" than anything else running on the network. But that was ok, because everything was behind a firewall. (Some sarcasm in those last bits, in case it wasn't obvious.)
Note that I'm not arguing that Sun was a leader in security, but they did make some efforts that other companies didn't.