Actually, RESTfulness only applies to RESOURCES, as indicated by a Universal Resource Identifier. So to even talk about things like headers, cookies, etc. in regards to REST is not really appropriate. REST can work over any protocol, even though it happens to be routinely done over HTTP.
The main determiner is this: if you send a REST call, which is a URI, then once the call makes it successfully to the server, does that URI return the same content, assuming no transitions have been performed (PUT, POST, DELETE)? This test would exclude errors or authentication requests being returned, because in that case, the request has not yet made it to the server, meaning the servlet or application that will return the document corresponding to the given URI.
Likewise, in the case of a POST or PUT, can you send a given URI/payload, and regardless of how many times you send the message, it will always update the same data, so that subsequent GETs will return a consistent result?
REST is about the application data, not about the low-level information required to get that data transferred about.
In the following blog post, Roy Fielding gave a nice summary of the whole REST idea:
http://groups.yahoo.com/neo/groups/rest-discuss/conversations/topics/5841
"A RESTful system progresses from one steady-state to the next, and each such steady-state is both a potential start-state and a potential end-state. I.e., a RESTful system is an unknown number of components obeying a simple set of rules such that they are always either at REST or transitioning from one RESTful state to another RESTful state. Each state can be completely understood by the representation(s) it contains and the set of transitions that it provides, with the transitions limited to a uniform set of actions to be understandable. The system may be a complex state diagram, but each user agent is only able to see one state at a time (the current steady-state) and thus each state is simple and can be analyzed independently. A user, OTOH, is able to create their own transitions at any time (e.g., enter a URL, select a bookmark, open an editor, etc.)."
Going to the issue of authentication, whether it is accomplished through cookies or headers, as long as the information isn't part of the URI and POST payload, it really has nothing to do with REST at all. So, in regards to being stateless, we are talking about the application data only.
For example, as the user enters data into a GUI screen, the client is keeping track of what fields have been entered, which have not, any required fields that are missing etc. This is all CLIENT CONTEXT, and should not be sent or tracked by the server. What does get sent to the server is the complete set of fields that need to be modified in the IDENTIFIED resource (by the URI), such that a transition occurs in that resource from one RESTful state to another.
So, the client keeps track of what the user is doing, and only sends logically complete state transitions to the server.