1 - follow the AWS API models, with a signed request using a private secret known only to the user and the server-side. You can see the S3 docs on RESTful auth using this approach. Also seems to recommend doing this over SSL.
2 - use SSL and send a userid/passwd or authentication key on each request.
In general, cookies are regarded as one of those "makes it not restful" type things.
I'd love to hear from HN'ers on how they handle RESTful authentication, particularly for projects where they are providing an API that is primarily consumed by a web app or other tool they implemented for users and have used RESTful api design as a design viewpoint.
Here's what I do for that case: Create a /sessions endpoint and POST to that when you login. The session resource will include a token of some sort identifying the session securely. The client can then authenticate to the API by passing this token via an HTTP header.