My standard operating procedure:
First, prompt the user for their email address or login name. If the information is not found, it's nice to tell the user that the address is bogus, but that can also help people brute-force this information. In systems where the login and email address are not identical, asking for either of these on the same page may be more user-friendly than separating them onto different pages.
Second, generate a unique token and associate it with the account. Send an email to the user's email address containing a link that integrates this token into the URL, allowing for one-click account retrieval.
Third, when the URL with the token is visited, prompt the user for their new password. Make sure the form submit also includes the token. Change the user's password to the new desired value, then invalidate the token.
A variation I've seen also adds a second token into the mail, which must be typed in on the resulting password reset page.
You should also invalidate the token after a reasonable period of time -- say, 48 hours.
You'll note a lack of password reminders or security questions here. If the user's email account has been compromised, this allows a potentially malicious user to hijack accounts. This isn't your problem to solve. You could add some sort of security question, but before you do, think about the last time you were confronted with one of these, and recall how much of a pain in the rear end they are.
If your system allows the user to be logged in from multiple places (it'd better!), you might want to make sure that the token(s) you use to permit this are tied to both the user's email address and password. This will log the user out of all other locations when either of these change.