There are a few different methods for this. A secure method would be to add a field to the mysql user table and have a "remember_me" hash which is just a random hash generated.
The hash should be stored in a cookie on the users computer as well as the userid for validation purposes for however long the remembering period lasts (you should also set the remember me period in the DB as a timestamp as well for extra security). When they pull up your site, you see if that cookie isset, if it is then you just authenticate the hash to the userid. If it validates they are considered logged in. If it does not validate, then send them to a sign in page / they are not considered logged in.
This is how I setup most of my sites. The pain is that if they login from another computer, well they are now no longer validated on the computer they were using and will have to re-authenticate. But security, to me, is more important than them having to login again due to that situation.
EDIT: See comments below for extra information regarding the sessions / security.
Does it involve adding a new column to the table in MySQL where all of the user information is stored, etc. ?
Not necessarily. A "remember me" works by storing in a cookie either the primary user credentials (his username and password, typically) or some temporary credentials that are set to expire after some time. If you use these temporary surrogate credentials, which are typically long random strings, you must add a table to your database where you store them, the username associated with them and the time where they expire.
You almost certainly do not want these credentials to be send over an unencrypted connection. You should store them in secure cookies, that is, cookies that are only sent over HTTPS (you should also set the cookie via an unencrypted connection).
If you choose to use a secure cookie but do not want to encrypt all traffic you can use two cookies:
Then, when the user visits your site and he's not logged in, you check for the presence of the unsecure cookie. If it exists, you redirect the user to a HTTPS page. Since this is secure, the secure cookie, with the user credentials, is sent by the client. You then proceed to check the content of the cookie with that you have stored in the database and login the user.
When someone logs in with 'remember me' set, generate an identifier, and store it on a cookie.
When someone visits a page on your site, look for a cookie. If they have one, look it up in your DB, where it should be mapped to a userid. Then just run whatever login functionality, just as if they'd entered a valid username & password.
