I see that the basic issue here is mixing up Session with State. And while REST specifies that you should NOT store the State on the server, nothing prevents you from storing a user Session.
Managing the State on the server means that your server knows exactly what the client is doing (what page they're viewing in which section of the application). And this is what you shouldn't need to do.
I agree with the other people saying that you should keep the session storage to a minimum size; and while that's common sense, it's actually also dependent on the application. So, in short, you can still keep a session with cached data to handle the requests with less load on the server, and manage the authentication by providing a temporary authentication/access token for the client to use. Whenever the session/token is expired, generate a new one and ask the client to use it.
Someone might argue that the client should better generate the token. I say it works both ways, and it would depend on the application, and who's going to work with the API.
Also keeping some sensitive session data on the server should be the right way to do. You cannot trust the client to keep their shopping cart that (for example) contains a field named "isFreeGift". Such information should be kept on the server.
The video link provided by Santanu Dey in his answer is helpful. Watch it if you haven't.
Just a side note: It seems all the answers already given seem to disregard the fact that some operations could cause a heavy load on the server. That's relevant in terms of power consumption, hardware consumption, and cost (for servers rented by CPU cycle). A good developer shouldn't be lazy in optimizing their application, even if the operation can be done very quickly on a modern CPU on some rented server for which they don't pay its electricity and maintenance bill.
Althoght the question is a few years old, I hope that my answer would still be helpful.