Cómo administrar el estado en REST

Supongo que esta pregunta sonará familiar, pero soy otro programador desconcertado por REST.

Tengo una aplicación web tradicional que va de StateA a StateB y así sucesivamente. Si el usuario va a (URL de) StateB, quiero asegurarme de que ha visitado StateA antes. Tradicionalmente, hago esto usando el estado de sesión.

Dado que el estado de la sesión no está permitido en REST, ¿cómo puedo lograr esto?