We have a REST application that is utilized mostly by applications that dont need to maintain their state, so till date we have been quiet "RESTFUL" without maintaining a state. We use the Private/Public (similar to Amazon) for authentication.Currently the client passes the credentials for every request
Now we have a new requirement where we have to maintain the state (or conversation).The client can be a Rich application or a hand held device .I am trying to comeup with the best way to implement the state .Should we pass on a session Id and maintain that ID ..is that the best and the only solution ?
Passing on a session ID is not the only way and not the best way to maintain conversational state. The best way, if you have a RIA is to maintain the state on the client itself, where it belongs, as some of the comments suggest. This means still sending the credentials every request.
Re-authentication on every request is the only way, and if you feel that there's a performance hit on the server, the server can (as suggested) cache the result of an authentication request for a period of time. Digest authentication could help avoid caching responses by cryptograpically signing the tokens going over the wire.
If that's not good enough you could use something akin to Google ClientLogin, and giving the client an encrypted token that can be verified without needing to ask an authorization, and without passing the user's real credentials over the wire. Google themselves this by doing the login over https, and then using the generated tokens over http. It's open for replay attacks for the lifetime of the token.