SAP NetWeaver has a password policy to prevent your new password beeing similiar to the last 5 passwords.
Are the passwords stored in plaintext to verify this?
Or is something like a soundex value stored?
They don't need to have the passwords in plaintext to be able to verify that.
They could be using the best practices(PBKDF2) and still be able to spot password re-use.
You have the password hash, the salt and number of iterations(e.g salt:iterations:hash). So all they have to do is keep the last 5 passwords run through PBKDF2 stored somewhere and run the same algorithm on new passwords along with the salts of old passwords and they can determine if the password was used before or not.
The downside here is that you can only check for exact match and even if a single character's capitalization has changed you won't be able to verify that for older passwords, but since you have to enter the current password to be able to change your pass, the application can have access to plaintext version of it at that moment and have more strict checks on your very last password. And this is what SAP does, you can't enter the exact same passwords you had before and you can also enforce the user to change at least "n" characters from their previous password in their new one. (Reference)
Hash algorithms have pseudorandom output and changing a single bit in the input makes unpredictable changes to the output. So apart from using salts, iterations or whatever even in case of simple hash algorithm use like md5 or sha-1, there is no way to measure the similarity between inputs, only having access to the hash output.
EDIT: The question was asking how matches are detected, the answer below is for similarity:
When using a good hashing algorithm, same or similar passwords will never have the same hash value. You can't check hashes for similarity, only for equality.
They could be using something like fuzzy hashing to check fundamental level of similarity which gives the percentage of similarity.