The relationship between client and server is not stateless in the majority of the cases. Most of the implementations rely on authentication state (cookie, session secret). Very few actually do the stateless part right.
The "simple" answer is to have client-certificates, and allow a client access directly to an application server over TLS, or use a secure transport (eg: IPSec), and just use standard HTTP auth on every pass (which AFAIK never was extended to use some form of standardized token, so one's left with sending the actual login/password pair every time).
The sane compromise is to just use encrypted cookies -- but they are also bolt on solutions.
The problem is that essentially one needs encryption to ensure secure sessions, which essentially boil down to authenticating the client to the server, and the server to the client, and forming some kind of session (typically DH for a symmetric session key).
For a long while, encryption was really expensive compared to the db lookup and template render that "every" web application did -- and so we've ended up with a mess of "best practices" which aren't very good at all (and not a very good way of moving from REST-that-trusts-plaintext-ip to REST-and-also-secure).
With HTTP/2 it looks like things are moving towards making the transport-protocol part do the things it should -- track the session, and secure the session. Still doesn't do a good job of authenticating the client in any meaningful way, but it should simplify some of the assumptions that are necessary to build a secure(ish) system.
As simple as that.
None of this requires state on the server.
I need to store a state somewhere at least. That’s not really stateless.
I'm not really convinced that's not a good idea for a TLS-only service (compared to the complexities that tokens/cookies introduce). One reason why there was a move away from Basic Auth was ofcourse that it is crazy to send plain-text login/password pairs over a plain-text transport (HTTP sans S).
And there's never been any working, cross-platform effort to improve things (AFAIK).
There's some work on Kerberos that's interesting, but again, many of these efforts have been simply co-opted by the fact that everyone used cookies (and had problems, and started encrypting them etc), and then moved from HTTP to HTTPS.
When you have HTTPS, there's not that many reasons to not just have "SECRET PASSWORD" in the URL (granted that'd not be REST either, but BASIC AUTH does the same thing, just in a header).
If you have to do a challenge-response auth every 5 requests, or so, to get a session, then it’s not really rest.
Client certificates might actually make the most sense in this case.
A good read: https://www.safaribooksonline.com/library/view/restful-web-s...