What algorithm should I use to hash passwords into my database?

First rule of cryptography and password storage is "don't invent it yourself," but if you must here is the absolute minimum you must do to have any semblance of security:

Cardinal rules:

1. Never store a plain text password (which means you can never display or transmit it either.)
2. Never transmit the stored representation of a password over an unsecured line (either plain text, encoded or hashed).
3. Speed is your enemy.
4. Regularly reanalyze and improve your process as hardware and cryptanalysis improves.
5. Cryptography and process is a very small part of the solution.
6. Points of failure include: storage, client, transmission, processing, user, legal warrants, intrusion, and administrators.

Steps:

1. Enforce some reasonable minimum password requirements.
2. Change passwords frequently.
3. Use the strongest hash you can get - SHA-256 was suggested here.
4. Combine the password with a fixed salt (same for your whole database).
5. Combine the result of previous step with a unique salt (maybe the username, record id, a guid, a long random number, etc.) that is stored and attached to this record.
6. Run the hash algorithm multiple times - like 1000+ times. Ideally include a different salt each time with the previous hash. Speed is your enemy and multiple iterations reduces the speed. Every so often double the iterations (this requires capturing a new hash - do it next time they change their password.)

Oh, and unless you are running SSL or some other line security then don't allow your password to be transmitted in plain text. And if you are only comparing the final hash from the client to your stored hash then don't allow that to be transmitted in plain text either. You need to send a nonce (number used once) to the client and have them hash that with their generated hash (using steps above) hash and then they send you that one. On the server side you run the same process and and see if the two one time hashes match. Then dispose of them. There is a better way, but that is the simplest one.

CodingHorror had a great article on this last year. The recommendation at the end of the article is bcrypt.

This 2008 answer is now dangerously out of date. SHA (all variants) is now trivially breakable, and best practice is now (as of Jan 2013) to use a key-stretching hash (like PBKDF2) or ideally a RAM intensive one (like Bcrypt) and to add a per-user salt too.

Points 2, 3 and 4 are still worth paying attention to.

See the IT Security SE site for more.

---

Original 2008 answer:

1. Use a proven algorithm. SHA-256 uses 64 characters in the database, but with an index on the column that isn't a problem, and it is a proven hash and more reliable than MD5 and SHA-1. It's also implemented in most languages as part of the standard security suite. However don't feel bad if you use SHA-1.

2. Don't just hash the password, but put other information in it as well. You often use the hash of "username:password:salt" or similar, rather than just the password, but if you play with this then you make it even harder to run a dictionary attack.

3. Security is a tough field, do not think you can invent your own algorithms and protocols.

4. Don't write logs like "[AddUser] Hash of GeorgeBush:Rep4Lyfe:ASOIJNTY is xyz"