I can think of the following two approaches:
1) Use regular HTTP sessions with cookies or URL rewriting.
This has the advantage that there is already support in the servlet API etc.
2) Use some kind of session token that the client must enclose with each request.
Since you are contemplating a RESTful web service, I guess the HTTP headers is the place to put such a token.
Interested in hearing about other approaches, if there are any!