First of all, please note that most people do not encrypt (as you wrote) passwords into their databases. Encryption, whether symmetric or asymmetric, means that the data could be decoded again. Encrypting passwords would be a very bad concept (at least if there would be a common key for all of them) because the decryption keys would have to be stored somewhere, and if an attacker would get hold of them, he could immediately decrypt all passwords.
What you want to do is called hashing. The hash of a password is derived from the password by applying a hashing function to the password. The key point here is that this process cannot be reverted, i.e. there is no mathematical method to get the password back from the hash.
Having said this:
MySQL's SET PASSWORD and PASSWORD() are deprecated. They will be removed in future versions of MySQL. If you want your application to run with future versions of MySQL, don't use SET PASSWORD and PASSWORD().
MD5 and SHA1 are definitely not the way to go; they are considered broken.
The SHA-2 family (e.g. SHA256, SHA512) is considered safe in a mathematical sense. Nevertheless, it has low computational cost / high speed, and today's consumer GPUs can compute multiple billions of SHA-2 hashes per second. Thus, for hashing passwords, other hashing functions like bcrypt, pbkdf2 or scrypt (which is my current favorite) are appropriate; these are designed to be slow (how slow can be adjusted which is a big advantage in the future) and (in case of scrypt) to consume much memory which makes hardware (ASIC, FPGA) based attacks more difficult.
I don't know PHP, but most languages have a function called crypt() or encrypt() or the like which uses the crypt() API of the underlying O/S (in Linux: glibc), so you could use this as a starting point, but only if it already provides one of the slow hashing algorithms (which mostly is not the case).
MySQL has a function called ENCRYPT() which also uses the OS's crypt(), but it is deprecated as well. MySQL also has a SHA2() function, but as mentioned above, this might not be sufficient. Unfortunately, MySQL (AFAIK) does not provide a BCRYPT(), PBKDF2(), SCRYPT() or any other well-known slow hashing function.
Since you should use one of the slow hashing algorithms, and since neither the OS's crypt() (in most cases) nor MySQL provide any of them, you should do the hashing in your back-end application. As said above, I don't know PHP, but I am quite sure that there is an implementation for at least one well-known slow hashing algorithm (which does not depend on the underlying OS's / libc's crypt()).
By the way, there will be no differences regarding the result between various implementations of hashing algorithms. For example, if you apply SHA512 to a string using your favorite programming language, the result will be the same as if you apply SHA512 to that same string using MySQL. The same is true for the other hashing algorithms, including the slow ones. There may be a performance difference, though.
That basically means that, if you now do the hashing in your application back-end, you can do it later in MySQL as soon as MySQL provides the slow hashing algorithm you are using. You can switch forth and back between hashing in the application back-end and hashing in the database withouth having to re-compute all stored hashes and without losing data.
Additional rules of thumb:
Don't even think of implementing your own login / password system before you have fully understood all references I gave.
If you are for some reason forced to use any other hashing algorithm than a slow one, always use salting, of course with a different salt per password. While some people proclaim that this is useless, I don't think so. It still will make attacks more difficult (compared to hashing without salt). But attacks against fast hashing algorithms like the ones from the SHA-2 family, whether salts are used or not, will still be extremely easy and efficient compared to attacks against one of the slow hashing algorithms.
Finally, here is a blog entry which should get you started. This will give you a feeling about what's important, but you'll have to do further research (it's four years later now ...).
