First requirement is proper salting. I already wrote about this so check that post for explanation. I will just say here that properly implemented salting strengthens password against whole range of brute-force attacks. Storing password without salting is just not acceptable.
Second requirement would be using proven algorithm. Very often people (myself included) fall into trap of using easiest way there is. In case of password hashing this is usually just SHA-1 hash function. While this is definitely better than plain-text passwords, it is not ideal. Password hashing is just not that simple. Minimum would be support for RFC 2898 password derivation (both PBKDF1 and PBKDF2 will do). For this purpose .NET offers Rfc2898DeriveBytes class.
RFC 2898 also defines way to make your password hashing slow (via iteration count). Although every programmer wants code to run fast, exact opposite is required for password hashing. Idea behind it is to slow-down dictionary attacks. It is huge difference between trying out 10 and 1000000 passwords per second. Of course, you also need to think about users so some compromise is needed. There is no exact figure but I find anything sub-500 milliseconds acceptable to users.
Last requirement that I would add is using user name as part of hashing process. This is to protect us from “copy/paste” attacks if user names and hashes cannot be secured (e.g. in database table). If user name is not encoded, one could copy known password1 hash from user1 to user2 (overwriting password2 in progress). After that it will be possible to login as user2 with password1. That allows user1 to potentially create mess and blame everything on user2. If he restores old password2 afterward, you have security breach that is not easily traceable.
If you are not in mood for implementing this, you can download example of my implementation.
I opted for 9-byte salt and 20-byte key. That results in 30 bytes of output (first byte is iteration count). With base-64 encoding resulting string is exactly 40 bytes long.
8192 iterations should cause function to be around 500 milliseconds on most computers (@ 3GHz). This was selected as user’s psychological limit on waiting. Since number of iterations is stored in first byte of hash (12 for 4192 iterations, 13 for 8192, 14 for 16384 and so on) you can also speed-up (or slow-down) code by factors of two and retain compatibility among different versions.
User name string is converted to upper case before hashing (or checking). This causes user name to be case-insensitive even when encoded.