Avoid MD5 for anything new. Its made people in the cryptographic community so nervous that they actually suggest using something from the NSA (namely, SHA1) instead of MD5. Its not outright broken, but it doesn't look too good.

If you can, use SHA1 instead. You'll need to grab Digest::SHA1 off CPAN.

The way I normally do it is to have a table containing usernames and a seperate related table (1-to-1 relationship) containing the encrypted password for that user. This is because it is more difficult (though not impossible) to carry out a cross-table SQL attack. The schema looks something like this:

CREATE TABLE secure_fields (
    id     INTEGER UNSIGNED PRIMARY KEY AUTO_INCREMENT NOT NULL, 
    salt   INTEGER UNSIGNED NOT NULL, 
    passwd CHAR(40) NOT NULL 
);
[download]

When encoded in hex, SHA1 produces a string 40 characters long. You can change the size of the passwd field for other encodings if you want.

Encoding the password looks something like this (in psudo-code):

plaintex_passwd  = The plaintext password from the user 
hex()  = Hex encoding function
SHA1() = SHA1 digest function
salt   = Random 32-bit value (doesn't need to be a cryptographically s
+ecure random num)
+      = String concat

hex( SHA1( salt + SHA1( salt + plaintext_passwd ) ) )
[download]

IIRC, MySQL's PASSWORD() function uses MD5, so avoid it.

IMHO, an often overlooked part of cryptography is that you need to code your application so that you can change crypto algorithms easily. In this case, that means you need to code so that you can replace SHA1 with something else if tommarow it turns out that SHA1 is totally broken. The Digest module is good for this purpose.

Update: Fixed typo.