Say a database server has a HSM which is in use for encrypting (reversibly of course) credit card numbers. Is there any way a HSM could be used to add strength to a password hashing scheme? (Or are there any password hashing schemes that make use of a HSM to be more secure than pure software schemes)
You could, instead of hashes, use a MAC. That's a kind of hash function except that it uses a secret key, which is needed to recompute it. You would store the key in the HSM. The HSM would be needed to verify the password; if an attacker steals your database, he still cannot run a dictionary attack. This kind of scheme is sometimes called peppering and a HSM is the right way to use a pepper. To defeat such a system, the attacker would have to hijack the HSM and use it to "try passwords".
You could hash the passwords, store the hashes, and perform all hash verification inside the HSM, so that no hashes reside on the machine that provides the rest of the service.
This provides a separation of duties, which may be useful in high security scenarios. In order to extract hashes for cracking, the HSM would have to be compromised.
However, this is a rather unusual use for a traditional HSM, which is usually utilised for storage of sensitive data which must be reversible into its original plaintext. The idea is that one single secure built-for-purpose device stores the encrypted data and keys, and can provide unencrypted data upon request.