I've just read a blog post suggesting ways to do user authentication on a REST based service, and - as is far too common - they got it totally wrong. They detailed a means to generate hashes based on the message and shared secrets that only that user would know.
REST is fundamentally based on a few things. One of these is to leverage the HTTP protocol wherever possible. You already see this in the use of HTTP verbs for actions, URLs to refer to resources, status codes for error handling, amongst other things. Following this through, logically the sensible way to do user authentication is to do HTTP auth. It's clearly defined by the HTTP specifications - RFC2617 is a decent place to start here - and gives exactly what is wanted. It also gives a number of different ways to manage how user credentials are sent to the server, and you get to define your own if you really need to. What more could you ask for?
The obvious problem with it is that the standard http auth mechanisms - basic and digest - can be vulnerable to man in the middle attacks. But there's an answer to that too. You should never send anything sensitive - like authentication headers - over plain http. Use https instead. It's so simple to set up these days, and certificates can be self generated or bought for really not very much, so there's no excuse not to!