Unless the data is really simple and you don't care if it's stolen, session data should always be stored on the server side, and only a meaningless identifier sent to the client.
Managing sessions on the server side used to be a PITA, to be sure, especially if you had multiple servers. But nowadays there are lightening-fast distributed key-value stores that are ideal for storing session data. No need to encrypt, base64-encode, base64-decode, and decrypt multiple kilobytes of data with every request. Think of all the bandwidth and latency you could save by not sending those kilobytes back and forth!