I have a question posted already for this issue in Windows systems, and thought that non-Windows systems should perhaps be covered separately.
In NIST SP 800-53 Rev. 3, IA-5 is the control addressing "Authenticator Management". The requirements in this control include such things as enforcement of password length, complexity, lifetime, history, and proper storage/transmission of passwords.
The first enhancement for this control, which is selected for all (Low/Moderate/High) systems includes this requirement:

The information system, for password-based authentication:
...
(b) Enforces at least a [Assignment: organization-defined number of changed characters] when new passwords are created;

In most systems, it's pretty easy to find and configure the rules that enforce long and complex passwords which are changed regularly and do not exactly match a certain number of old passwords.  But, how do you implement a policy that requires a certain amount of characters to be changed with every new password?
Some systems I'm interested in (feel free to address others):

Mac OS X
Linux/Unix (Any/all flavors)
Cisco IOS


I'm not sure about comparing with all the passwords the user has previously used, as it really depends on the hashing system your using and I would say if its possible to derive any similarity from the hash then its not a very good system to begin with.

But assuming that the user has to supply their current password when setting their new password, you could at least check the new one against the current one as you'll have both as unhashed at that point. 

The pam_cracklib module on Linux checks passwords like this and does a few basic checks by default. 


Is the new password just the old password with the letters reversed ("password" vs. "drowssap") or rotated ("password" vs. "asswordp")?
Does the new password only differ from the old one due to change of case ("password" vs. "Password")?
Are at least some minimum number of characters in the new password not present in the old password? This is where the "difok" parameter comes into play.


You can find some more details about it here.
