Stateful системы
Такие системы хранят внутри себя состояние, которое влияет на запросы от пользователя. Примером могут быть сессии пользователей, которые хранятся на сервера. Ответ на запрос пользователя зависит от состояния сессии.

Одна из основных проблем таких систем — горизонтальное масштабирование. Чтобы развернуть несколько экземпляров сервиса нужно как переносить состояния но новые машины и синхронизировать их. Но проблема относительно легко решается за счет внешнего хранилища в котором можно хранить сессии. Система все равно является stateful, но сами веб сервисы стали stateless и теперь можно спокойно их масштабировать.

Stateless системы
Как альтернативу сессиям можно использовать cookie файлы или JWT токены. В таком случае вместе с запросом мы всегда отправляем всю необходимую информацию для его выполнения и аутентификации. В таком случае серверу не нужно хранить информацию о пользователе, достаточно проверить на валидность куки или токен в запросе. Так что stateless система зависит только от данных которые ей были переданы, а не от внутреннего состояния.

Еще один пример системы, которая хранит состояние: у нас есть интернет магазин. Пока корзина пользователя храниться в памяти сервера — это stateful. В таком случае мы опять упираемся в проблему с масштабированием. Но мы можем вынести состояние корзины в базу данных, тогда сервис станет stateless и можно легко его раскатывать на несколько машин.

Более детально расписано тут: stateless/full web service