I updated my Apple-ID password after losing my Mac. Will Find my Mac still be able to find it? If so, how does the authentication/identification work?
Yes, Find my Mac still work except someone re-format the system and active Find My Mac with a new Apple ID.
the authentication is token, not the password of your appleID when active Find My Mac. this information saved in NVRAM, you can check it out with this command,
sudo nvram -p |grep FMM