What security measures should be taken when creating "change your password" functionality?

Question

I'm adding a "change password" functionality to my webgame http://ninjawars.net , which currently has fixed (and essentially never changing) passwords.

I want to avoid making a mess of it, so I'd like to make sure that I have the basic security bases covered.

Taking what I can pull from facebook's way of doing things, a few points that key points to remember are:

• Require old password (of course).
• Confirm new password input twice.
• log off the account (only on all other pages, somehow)?
• Require a secure password length & that the password fits all the [insert various criteria here] required for passwords on each specific system.
• Require new password to differ from old password.
• Prevent multiple password change attempts.

Facebook also:
- Requires new password to be different from past passwords. (seems like an edge case use)

Those are only the policies that I can glean from the outside UI of facebook's account system. What other security points should I cover when providing a "change password" system?

Edit: In my specific case I intend to be relatively permissive with the [insert various criteria] for what characters will have to go into the password itself. My site isn't a bank, if a player wants to use the password "password1", then they should expect their account to be taken over by their friends. MY FOCUS on the other hand, is on making sure that my site prevents any opportunities for "hostile takeover" via any kind of insecurity in the password changing system itself.

More good points from the answers below:

• Send notice of password changes to user's email.
• Keep change of email and change of password each dependent on each-other.
• Use a secure encrypted (https) connection for such changes.

Answer 1

Keep the changing of the password and any changes to the e-mail address separate. That way anyone wanting to change either has to know both.

When the user requests a password change e-mail them the link to the page. This will confirm that they are the owner of the account and alert them if someone is trying to access their account. Then when the password has been changed e-mail them the confirmation.

Answer 2

This is probably obvious, but remember to do the whole password change process over an encrypted connection (HTTPS).

Answer 3

One thing I see occasionally is to send an automated e-mail to the e-mail on file notifying of the password change. This would give a chance/link for the recipient to revert the changes if they were done unintentionally or maliciously. Obviously this would require a similar warning period for changing e-mail addresses to provide any more security.

Answer 4

I noticed noone has suggested this yet, or I'm missing some of the subtleties in other's answer.

Only allow changing the password only if the user knows a "secret string" that will be sent to their email address when they request a password change. For convenience, you can make this "secret string" as an URL, so they can just quickly click it on their email. This ensures that the person requesting change of password can also login to the registered email (people tend to be more relaxed with their game account than their private email address).

As ChrisF has mentioned, you will have to ensure that the person cannot both change password and email simultaneously. You will also need to ensure that changing the email requires knowledge of the current password (you probably should not require that the user can login to his old email to read a "secret string", since the primary reason for changing email address is because they lose their old email address).