Stateless - сервис не хранит состояние между запросами; каждый запрос обрабатывается независимо. Масштабирование горизонтальное, отказоустойчивость проще. Сессию выносят в Redis/БД.
Stateful - состояние хранится на сервере (сессии в памяти, sticky sessions). Сложнее масштабировать и балансировать. Используется когда нужна тесная привязка к состоянию (например, WebSocket-сервер).