First of all, REST is not a religion and should not be approached as such. While there are advantages to RESTful services, you should only follow the tenets of REST as far as they make sense for your application.
That said, authentication and client side state do not violate REST principles. While REST requires that state transitions be stateless, this is referring to the server itself. At the heart, all of REST is about documents. The idea behind statelessness is that the SERVER is stateless, not the clients. Any client issuing an identical request (same headers, cookies, URI, etc) should be taken to the same place in the application. If the website stored the current location of the user and managed navigation by updating this server side navigation variable, then REST would be violated. Another client with identical request information would be taken to a different location depending on the server-side state.
Google's web services are a fantastic example of a RESTful system. They require an authentication header with the user's authentication key to be passed upon every request. This does violate REST principles slightly, because the server is tracking the state of the authentication key. The state of this key must be maintained and it has some sort of expiration date/time after which it no longer grants access. However, as I mentioned at the top of my post, sacrifices must be made to allow an application to actually work. That said, authentication tokens must be stored in a way that allows all possible clients to continue granting access during their valid times. If one server is managing the state of the authentication key to the point that another load balanced server cannot take over fulfilling requests based on that key, you have started to really violate the principles of REST. Google's services ensure that, at any time, you can take an authentication token you were using on your phone against load balance server A and hit load balance server B from your desktop and still have access to the system and be directed to the same resources if the requests were identical.
What it all boils down to is that you need to make sure your authentication tokens are validated against a backing store of some sort (database, cache, whatever) to ensure that you preserve as many of the REST properties as possible.
I hope all of that made sense. You should also check out the Constraints section of the wikipedia article on Representational State Transfer if you haven't already. It is particularly enlightening with regard to what the tenets of REST are actually arguing for and why.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…