Also, though less of an issue with SSL, the HMAC approach is subject to replay attacks while expire_at < now.
EDIT: The HMAC approach also lacks any method to invalidate cookies manually, or automatically e.g. when the user changes their password. This means a compromised account is open to attack until expire_at < now, and there's nothing you can do about it other than blocking the account for that duration, which now means that each request needs to do a database lookup to see if the account is blocked. You could generate a per-user secret key, but now you have a database lookup again, so you might as well use the magic number scheme.
Replay-attacks work the exact same whether you use this scheme or store a magic number server-side. There's no difference whatsoever.
For a password-change you update the last_logout timestamp and hand the user a new cookie (since his current one was just invalidated).