I go with the rest - only store a sufficiently large and random number in the cookie, and store the rest on your server. (That also adds the ability to update the data structures in the cookies).

However - if you're really concerned about security, remember to use https. That will prevent whoever's eavesdropping from catching your cookie! (This has become much easier since WLAN became popular and "easy-to-use")