A stateless service holds no client-specific state between requests — everything it needs comes in the request or from a shared store (database, cache). Because any instance can serve any request, statelessness is what makes horizontal scaling and simple failover possible.
Worked example: a stateless API server stores session data in Redis, not local memory, so a load balancer can send a user’s next request to any instance and a crashed instance loses nothing. Gotcha: truly stateless is a design discipline — in-memory caches, local file uploads, and sticky sessions sneak state back in; pushing state to a shared store adds a network hop but is what lets you add, remove, and restart instances freely.