Can't anyone implementing a webclient and webservice on top of common web servers and browsers, choose to forgo cookies and keep the state server side? If this is so, then why do people choose to use cookies if they give more overhead?

Also you would need to keep some sort of unique identifier on the client, that the client can send the server, in order for the server to be able to look up the session state (a session id). Isn't this what cookies often are used for? I'm guessing this is probably what you meant "information-free session nonces" would solve above. This sounds interesting, could you explain this scheme to me or maybe point me in the direction of a good resource?