The things that can be implemented with the standard password policies are described here.
One of the possible options is to prevent reusing passwords. The administrator can set how many old passwords are saved. As far as I am aware this only prevents users from using identical passwords, it does not prevent them from using identical passwords.
Another possibility is that the password could be stored with reversible encryption. This is another standard option that can be set on a domain. Most security experts suggest that enabling this is a very bad idea.
You asked how a system could do this.
I see that it offers the option. This
is more of an academic question,
though - any ideas on how it works
vis-a-vis the hashing described above?
When the password changes are made a reversible version of the password is transmitted to the domain controller. There are hooks where an application can intercept the password change request and get an unencrypted version of the password. Here is one OSS project that provides a hook (http://passwdhk.sourceforge.net/).
Presumably, the mentioned grabs the passwords they are being changed and then stores them using a reversible encryption. When the password is being changed the application would probably decrypt all the passwords and use something like the levenshtein distance to see if the passwords where different enough.