All you need to store is a something that identifies them, that can't be forged. As a simple (non-secure) example, you could put their user name in a cookie. Then, when someone who does not have a session requests a page, check the cookie for their user name, go through the log in procedure as if they'd supplied a password and then continue as normal. Of course, the problem is that anyone can create a cookie with a certain user's name and log in for free then.
You need some piece of data that no one else can guess. If you know no one will see your code, make a single, long, randon string. Concatenate it with the username and do some sort of a one way hash on the result (like sha1). Store that in the cookie and when you analyze the cookie like above, use the same string and algorithm, compare the results and if they match, they're in. (You'd also have to store the user name in plain text in the cookie or another one so that you know who you're trying to authenticate).
If people might see your code and get your random key, you've got to generate it on the fly and store it, maybe in a database with one key per user or something. Since you've probably already got password hashes in the database, you could use that as a key. Just be sure you don't accidentally expose something that would allow someone to crack a password with the data from a cookie you hand out.