But it seems to me that ReST does dictate, specifically, that there must be no need for shared state. The system must work without the client having knowledge of the server and vice versa. But a cookie, as used to hold a session token which references information on the server, is very much shared state. So should be forbidden.
The state is passed back and forth. The server does not keep the state (that is why they call it stateless), the client may keep it. If something does need to be stored on the server a resource should be created. The state that is passed back and forth may then contain a reference to the resource, a resource identifier (in case of the web usually a URI is being used).
The server is stateless because it receives the latest state from the client (location, cookie and other headers) and sends an new updated state (location, set-cookie and other headers) to the client again along with an optional representation. There is no need for the server to keep the state in memory anymore. Because the server does not keep the state it does not matter which copy of the server (in case of load-balancing or fail-over etc.) handles the next request as everything needed can be derived from the state sent along with request from the client.
Keep in mind that it is best practice to be able to reproduce a representation by the use of a resource identifier, like with "pure functions" in functional programming, it should be deterministic. The content of a representation may change but not the semantics of it.
The part that is stateful is the state that is being passed back and forth between the client and the server.
