If you only need to provide authentication but the data transmitted over the wire is not sensitive then there is a better way without the overhead/latency of SSL.
Say you have a mobile client app; first make the user sign up or register by providing their email(username) and password in a separate web form (not part of the app or REST service). Then upon successful registration you respond with a user key (this can be a shared secret key stored in the user account on the server (database) for symmetric encryption or a public key for asymmetric encryption where the corresponding private key is stored in the user account on the server (database). This is all done using a web form over SSL.
Now when the user opens the client app you must ask them for their credentials which will be sent with every request to the RESTful service. They must provide their name, password and encryption key which they received previously. This need only be done once. The app then provides some http header with each request which looks something like this:
AUTHENTICATE> username:timestamp:encrypted{password:timestamp} /AUTHENTICATE>
Note that both the password and timestamp inside the {} is encrypted using the user's key. The timestamp is updated with every single request.
Implement an authentication filter on the server that does the following:
First check the timestamp and if expired (say older than 1 second) send an UNAUTHORIZED HTTP response code. If the timestamp is valid lookup the username in your user account database. If not found send an UNAUTHORIZED HTTP response. If the username is found, fetch the stored encryption key for that user (remember this can be a shared secret key or the private key for the users public key). Decrypt the encrypted {password:timestamp}. The decryted password must match the users password stored in your database (the password itself could also be encryted in the database using another key for added security) and the decrypted timestamp must also match the non encrypted timestamp sent in the AUTHENTICATE header above. If not then send an UNAUTHORIZED HTTP response code. If successful the request has been authenticated without the use of cookies/sessions.
You can also cache the the user details to avoid doing a database lookup with every request.
Now if someone is snooping and intercepts the request they will not be able to re-use it to gain access because either the timestamp will be invalid or ,if they update the unencrypted timestamp to be valid, it will not match the encrypted timestamp (after the authentication filter decrypts it).
Another advantage of this approach over using a single app key is that you now have complete control over who can access your service by putting an expiry date on the user account in the database (effectively implementing a subscription based service). This is great because at first you may want to get as many users as possible with a trial subscription (free for say 1 year) then later block access to that user if they haven't payed up to extend the account expiry date :)