The answer is that your application (in a REST scenario) simply doesn't keep track of what happens. All state is managed by the client, and state transitions are effected through URI navigation. The "State Transfer" part of REST refers to client navigation to new URIs which are new states.
A URI accessed with GET is effectively a read-only operation as per both the HTTP spec and the REST methodology. That means if the client "backs up" to some previous URI, "the worst" that happens is another GET is made and more data is loaded.
Let's say the client does this (using highly simplified pseudo-HTTP)...
GET //site.com/product/123
This retrieves information (or maybe a page) about product ID 123, which presumably includes a reference to a URI which can be used to POST that item into the user's shopping cart. So the user decides to buy the item. Again, it's oversimplified but:
POST //site.com/shoppingcart/
{productid = 123}
The return from this might be a representation of the shopping cart, or a reference to the added item (which could be used on the shoppingcart URI with DELETE to remove the item again), or a variety of other things (such as deeper XML describing the cart contents with other URIs pointing to the cart items and back to the original products). It's all up to you.
But the "state" is defined by whatever the client is doing. It isn't tracked on the server at all, although you will certainly keep a copy of his shopping cart contents in your database for some period of time. (I once returned to a website two years later and my shopping cart items were still there...) But it's up to him to keep track of the ID. To your server app it's just another record, presumably with some kind of expiration.
In this way you don't need cookies, and javascript is entirely dependent on the client implementation. It's difficult to build a decent REST client without script -- you could probably build something with XSLT and only return XML from the server, but that's probably more pain than anyone needs.
The starting point is to really understand REST, then design the system, then build it. It definitely doesn't lend itself to building it on the fly like most other systems do (right or wrong).
This is an excellent article that gives you a fairly "pure" look at REST without getting too abstract and without bogging you down with code:
http://www.infoq.com/articles/subbu-allamaraju-rest