The problem is, if the token is deleted and you make a new one then the token on another machine would no longer be valid. So that means you must either store multiple tokens for any given user, or you have to use the same token on each machine.
Storing may increase the chances of brute forcing, but then again storing one may also increase the chances of brute forcing.
You could store multiple and then check user agent strings on each one. That way at least if someone did manage to brute force a key, if they weren't using the same browser it wouldn't be valid. This seems like your best option. You should salt the token with something user-unique, like their username or user id, email, etc. That way if you store it as md5 or sha1 a rainbow table attack wouldn't be as feasible.
For a table design, something like this:
CREATE TABLE `autologin` (
`user_id` int(10) unsigned NOT NULL,
`token` varchar(40) NOT NULL,
`ip_address` varchar(40) NOT NULL,
`user_agent` varchar(255) NOT NULL,
`time` int(10) unsigned NOT NULL,
PRIMARY KEY (`user_id`,`token`)
When they login, store this data:
// user_id = their user id
// token = sha1($a_salt . uniqid(mt_rand(), true));
// ip_address = $_SERVER['REMOTE_ADDR'];
// user_agent = $_SERVER['HTTP_USER_AGENT'];
// time = time()
Store token in a cookie also. Now when they try to autologin:
$token = $_COOKIE['token'];
// WHERE token='$token' AND user_agent='$_SERVER['HTTP_USER_AGENT']
// JOIN users ON id=user_id
You can optionally check that the IP's match, and set an expire time as well.
Hope that gets you in the right direction.