There are several different approaches you can take.
The RESTful purists will want you to use BASIC authentication, and send credentials on every request. Their rationale is that no one is storing any state.
The client service could store a cookie, which maintains a session ID. I don't personally find this as offensive as some of the purists I hear from - it can be expensive to authenticate over and over again. It sounds like you're not too fond of this idea, though.
From your description, it really sounds like you might be interested in OAuth2 My experience so far, from what I've seen, is that it's kind of confusing, and kind of bleeding edge. There are implementations out there, but they're few and far between. In Java, I understand that it has been integrated into Spring3's security modules. (Their tutorial is nicely written.) I've been waiting to see if there will be an extension in Restlet, but so far, although it's been proposed, and may be in the incubator, it's still not been fully incorporated.