Like I said; a two-part cookie.
eWWQajpgNxVBNckdAutX28kuovPXGwrv455SkCDQRUnwcNwbunuSzqE5Z3IGLdB4. There are two parts there: each part consists of 24 random bytes base-64 encoded. The first part is therefore
eWWQajpgNxVBNckdAutX28kuovPXGwrv and the second is
You could include a user identifier in that cookie as well. Not necessarily the username, since it would be hashed in the cookie. That would be an even more persistent component (because they're still the same user from one "Remember Me" to the next: remember that they might logged in on more than one device, and they might all have "Remember me" set).
Server-side, you'd have a cookies table;
userid | useridhash | persistent | varying, and that cookie would be stored there as
42 | HvUVkw1DCT9+ZhlVsuhQcU9AfyzUSVygzwOiIQ== | eWWQajpgNxVBNckdAutX28kuovPXGwrv | 455SkCDQRUnwcNwbunuSzqE5Z3IGLdB4 as you'd be searching for particular parts.
Since you're storing the userid hash directly, you'd probably wish to salt it, rather than have user 42 identified by the hash of '42'.