stateless - как и весь http подразумевает без запоминания состояния.
Собственно, нет разницы будут вам присылать login:password или токен привязанный к этому логину - всё равно придётся аутентифицировать. Лезть в базу и проверять есть ли такой токен и прочее. Просто чтоб не светить логин и пароль при каждом запросе (basic authentication) принято отсылать токены привязанные к этому логину.
Я предпочитаю в хедерах отправлять/получать токены, так url остаются чистыми, чем когда токен передают в url параметре как у facebook сделано.
Можно конечно кешировать, самое простое это HashMap с TTL в качестве ключа токен, в качестве значения - юзер. Проверять вначале HashMap на предмет, есть ли такой ключ с присланным токеном, если есть забираем юзера - если нет лезем в базу.
В spring можете сделать
interceptor где можно проверять токены, если всё нормально пропускать запрос дальше.
Можно сделать аннотацию, и вешать её на контроллеры или методы которые хотим аунтефицировать и в интерцепторе вначале смотреть есть ли аннотация используя Reflection API.
Простой
