There are a few different ways to check whether users' old and new passwords are similar, and each has its own strengths and weaknesses.
String Permutation Comparison
The first approach relies on creating a list of permutations that are not allowed. This might be a list of regular expressions or some similarly defined string changes that you evaluate passwords against. For example, you look for a number in the password and increment it, you look for a month name and try the next month name, etc. The altered new password is then compared to the old password to see if they match.
This can quickly become complicated if you're trying to come up with your own list of forbidden modifications because you need to define a minimum baseline of what transformations pose too great a security risk. If you want some ideas you can look at the appendix of this paper from UNC researchers where they list the transformations they used to compare the password histories of users. That paper is also a great resource for establishing the extent of password history similarities in a normal environment.
Algorithmic Comparison
As an alternative to creating a list of rules, you can evaluate an algorithmic comparison of the two passwords, like the Levenshtein distance or Hamming distance. This allows you to pretty much say 'I just don't want the passwords to be more similar than X' where X is some minimum value of change that you decide. This works pretty well to stop people who are doing things like going from "Muffins10" to "Muffins11" but not as well if they're going from "August14" to "November14".
This article discusses evaluating Levenshtein distance values of passwords in the context of making password cracking rule improvements, but it provides a decent overview (and code) of how this evaluation takes place.
Character Mask/Topology Comparison
A third option is to forgo looking at characters specifically and look instead at the character format. You can convert characters into their respective character types, creating a mask or topology. The password "Muffins10" would become ULLLLLLDD (with U = Uppercase, L = Lowercase, D = Digits, S = Symbol). Then you can prevent a user from choosing a new password with an exact or similar mask to their previous password.
This is a very aggressive policy to implement because it also prevents you from going from "Muffins14" to "Lovedog90" even though they don't appear to be related (unless your dog is named Muffins). KoreLogic has been working on implementing this in their PathWell Topologies project, albeit as part of a larger effort to prevent use of less secure password masks at any point. I believe their system allows you to prevent reuse of masks between the new and previous passwords.
Probably the biggest challenge with any of these approaches is communicating to users why their new password choice was rejected. Do you give them a generic error that the passwords are too similar or do you specifically call out why the new password isn't acceptable?
Some users may struggle to choose a acceptable new password under these systems unless you guide them through correcting the problems. You can offer instructions on how to create better passwords, but this will involve changing habits for a lot of people and will likely be met with resistance.
How To Compare Historic Passwords
Ok, so how do you make these comparisons when you only have a database of strongly hashed historic passwords and not the plaintexts?
During the password change process you will probably already prompt the user for their existing password as well as their new password, which provides you with the chance to compare those two in plaintext. That addresses the immediate evaluation and probably is effective enough against password similarities in the long term for most users. However, you may have some users that figure out that they can rotate between two different password variations every other password: Muffins10 --> 11Cupcakes --> Muffins12 --> 13Cupcakes
If you are really worried about that threat you unfortunately don't have a lot of options. You can use a string permutation approach to convert the new password with each rule, then hash it, and look for hash matches in that user's history. Neither of the other two approaches are compatible with hashed passwords. EDIT: Actually, I realized a character mask/topology approach would still work if you stored the historic mask (ideally encrypted) either alongside the historic password hash or instead of it.
But if you are using one of the recommended 'expensive' hashing algorithms then running through your rules and hashing several hundred results is going to use a lot of processing time. Will users tolerate a 5 second, 10 second, or longer delay before finding out whether their password was accepted? That is quite a change from the norm and may not be acceptable for some organizations.
The alternative to this is not hashing password histories but instead encrypting them. You can maintain only a hash for the current password, but during the password change process you would store the expired password as an encrypted data blob. This would allow you to decrypt historic passwords during the password change process and use any of the approaches to look for password similarities.
In theory it isn't terribly risky to store previous passwords using encryption. Both because encryption does work pretty well when properly implemented, and because the old password is no longer valid so knowledge of it shouldn't provide attackers with much advantage. This is especially true after you've implemented measures to prevent similarities between current and past passwords.
I fully recognize some people may not see this as an acceptable alternative since it would place the password history at a slightly greater risk of disclosure. However, I am not alone in seeing the benefits of using encryption in this situation, as this paper explains.