QUESTION: Most services require user to login before exploring further. If cookies are not recommended in REST, does it mean I have to go thru authentication on every single request (e.g., HTTP AUTH)?
ANSWER: There are two basic approaches here. The first is, use HTTP AUTH. The (human) user will be prompted for the credential just once (or they will be loaded from file, depending on the system at hand). The client software will compute the Base64 encoding of the credentials and will include them in each future HTTP request to the server (using the "Authorization" HTTP header).
The second alternative is to create a dedicated login service, that accepts credentials and returns a token. This token should then be included, as a URL argument, to each following request (e.g., by addding "&authtoken=XYZ" to the URL). Of course, the API (including the argument's name) should be clearly defined.
Each approach has its benefits, and its limitations. The first approach is easy to test using browsers. Just connect to the service with your browser, and on the first visit, you'll get a the username/password prompt. The browser than caches your credentials and automatically sends them on all following requests (just like the REST client software would have done!). The main advantage of the second approach is that tokens can be created with an expiration date (managed on the server, unlike cookie expiration). For some services, this is important.
And what about cookies? As I said elsewhere, these violate the "state transfer" notion of REST, where the complete state should be passed with each request. While cookies can be limited to function just like the Authorization header, why do that when you have a dedicated, special-purpose header?