If one could decode md5, it would be useless. The point of it is that it's undecodable 🙂
Say, you can store user_id AND an md5 string in cookies, and store the md5 string in your user table. Be sure NOT to make them (ID, md5(ID)), but think of smth more complicated (say, (ID, md5(username.ID.microtime())) or anything.
hen you just search for a row
SELECT * FROM users WHERE user_id = $user_id AND unique_string = $md5
Yes, there are other functions besides md5(). Look in the manual, they should be there.