I guess this question will sound familiar, but I am yet another programmer baffled by REST.
I have a traditional web application which goes from StateA to StateB and so on.
If the user goes to (URL of) StateB, I want to make sure that he has visited StateA before.
Traditionally, I do this using session state.
Since session state is not allowed in REST, how do I achieve this?
There are 2 REST answers to this, depending on what specifically you are trying to do.
If you are truly trying to manage request-based state (such as when a user is working through a multi-screen wizard or some other navigation-based workflow), then the REST answer is that state should be sent back-and-forth with each request/response (using something like a hidden text field, a query string, or POST data stored in a form). This is an implementation of Martin Fowler's "Client State" design pattern (detailed in full in his book, Patterns of Enterprise Application Architecture; see here for a reference).
If you are, on the other hand, trying to manage some sort of new object on the server--such as a shopping cart--then the REST answer is that you are actually creating a new entity that can be accessed like any other by a direct URL. Whether or not you store this new entity in a database or in application memory (like a traditional Session object) is up to you, but, either way, the new object is less about "state" on the server and more about creating a new entity for the user to interact with.