A common approach would be to use a strong encryption algorithm to store a cookie containing the following information on the user's computer:
AES([Expiry date] + [random salt] + [Username] + [Password])
That would allow the user to invalidate the cookie (if it was compromised) by simply changing their password. Encrypting it allows the site operator to verify that it has not been tampered with (extending the expiry date, for example), as well as protecting the clear text password from compromise. Including the password means that an attacker who gains access to the AES key can still not "mint" tokens to authenticate as arbitrary users.
The downside is then that the site has to protect an AES key.
An alternative approach would simply be to add two fields to your user database, for a cookie value (long/strong/randomly generated value), and an associated expiry date. Any user presenting that cookie would be authenticated, up to the expiry date. One would just need to make sure on the server side that operations such as changing a password removes any "remember me" cookies stored in the database.
Advantages of this approach are that there is no encryption key to manage (or worry about rolling over), and that there is no possibility of the user's password being compromised. Disadvantages are that you need additional storage for your users.
On the further plus side, this approach allows you to provide different "remember me" tokens on different devices (a la Google Account manager), simply by storing the tokens in a separate table and allowing more than one entry per user. This then makes it possible to track where each is used from, and invalidate them individually.