Como gerenciar o estado no REST

Eu acho que essa pergunta vai parecer familiar, mas eu sou outro programador perplexo com o REST.

Eu tenho um aplicativo Web tradicional que vai de StateA para StateB e assim por diante. Se o usuário acessar (URL do) StateB, quero ter certeza de que ele já visitou o StateA antes. Tradicionalmente, faço isso usando o estado da sessão.

Como o estado da sessão não é permitido no REST, como faço para conseguir isso?