It is actually easy.
chsh is a set-uid program:
$ ls -l /usr/bin/chsh -rwsr-xr-x 1 root root ... /usr/bin/chsh ^ +--- see the 's'!
So the program is run with the effective UID of root.
Now, how does it know which user is calling it? Because set set-uid changes the effective UID, but not the real UID. By comparing the real UID with the
passwd line you want to change, it can check whether you are allowed to do that.
Remember that a normal user can only change its own line, while the real root is allowed to change anyone's.
For more details, see the man pages for
geteuid and the other functions linked there.