Stateful means state is stored in memory or on disk by the processing service. Stateless means that state is stored distributed to multiple nodes and can be recreated or that there is a design such that no state is needed. In the first case, a node dies and information is lost, in the latter, no information is lost. This allows for greater scale by often saving resources per request and increasing resilience.
A concrete and simple example: an api request comes in and you call n dependent services before responding. If any of those calls fail, the entire response 500s, if ok, respond 200. Instead, make this a job with a 202 response with an id returned and use a distributed queue and workers to async process the request and allow the job results to be queried by job id. Now any node failures are invisible to the client.
