2 of 7 emphasis on how the comparison is possible at all

This is a feature of the PAM system which is used in the background of the passwd tool.

More specifically, pam_cracklib is a module for PAM which allows to reject passwords based on weaknesses.

Since you supply both old and new password, they can be easily compared.

The source code has various examples of what can be checked, e.g. whether a password is a palindrome or what the edit distance is between two words. The idea is to make passwords more resistant against dictionary attacks.

See also the cracklib manpage.