REST - это набор соглашений о том, как реализовывать API поверх HTTP. Оно включает как кучу деталей собственно интерфейса, так и принципы работы серверной части (идемпотентность, отстутствие состояния и прочее). Нужно это для того, чтобы при организации взаимодействия с очередным сервисом не реализовывать очередной набор костылей, а воспользоваться имеющимся.
В качестве примеров проблем, решаемых подходом REST можно выделить следующие:
- различие в схемах запросов (например, создание одного объекта через POST JSON а-ля RPC вконтакте с указанием метода, а создание другого - через GET причем с телом XML)
- различие в сообщениях об ошибке (HTTP 200 OK {"message": "internal server error"})
- различие в форматах ответов (без query-параметра id=1 возвращается список всех объектов, с query-параметром - словарь, содержащий один объект)
Про stateless пример привести не могу, не сталкивался в этом веке с такими API.
