Стоит ли хранить зашифрованные данные в cookie?

Я думал как раз об этом. Только все мне известные механизмы сессий обычно хранят данные на сервере, как вы уже сказали.

Стоит ли хранить зашифрованные данные в cookie?

Хорошо, а если записывать только какие-либо уникальные значения небольшого размера? Например id пользователя, темы оформления или значение капчи.