I am working on a REST API that will be used by developers writing mobile apps. Users will be able to use 3rd party services (Google, Twitter etc) to authenticate themselves, this is mainly handled by OAuth (depending on the service in question). We use 2-legged OAuth between the client application and the API Server (where the consumer key/secret is app specific, the developer gets it from our site when the app is registered there).
My problem is how to handle to keep track of the user authentication in a stateless manner. I do not have the users credentials to send in each request. I could create a unique session_id when a user logs in and then require that in each request to the REST API. Are there any other solutions to my problem? Does using a unique session_id to identify the user cause any problems from a stateless REST API perspective?