How should user passwords be stored?

Only as salted hashes using algorithms designed to be slow, like bcrypt or argon2, so stolen databases stay useless. Any system that can email you your old password is storing it wrong. Better yet, modern auth libraries make doing this correctly the default.