TL;DR: A stateless service keeps nothing between requests that only it knows, so any instance can serve any request and any instance can be destroyed without loss. State still exists; it lives in a database, a cache or the request itself. Autoscaling, rolling deploys and spot instances all depend on this.
How to approach it
Correct the phrase early, because "stateless" sounds like "has no state" and that is never true of a useful system. The precise claim is that the instance holds nothing unique. Then list what breaks when it is false, since that is the argument rather than the definition.
A strong answer
A stateless service can answer any request without relying on anything it kept from a previous one. The state is somewhere shared: a database, Redis, object storage, or carried in the request itself as a signed token.
What that buys, and each of these is a thing you lose without it:
Any instance can serve any request, so a load balancer can send traffic anywhere and does not need sticky sessions. Sticky sessions are the compromise people reach for, and they distribute load unevenly and still lose the session when the instance dies.
Instances are disposable. Autoscaling can remove one mid-traffic. A rolling deploy can replace them one at a time. A spot instance can be reclaimed with two minutes' notice. Every one of those is safe only if killing an instance loses nothing, and every one of them is a cost saving or an availability property you forfeit otherwise.
Scaling is horizontal and linear. Add instances, get capacity, because nothing has to be coordinated between them.
Recovery is trivial. A crashed instance is replaced rather than repaired, and nothing needs to be recovered from it. The blast radius of losing one is the requests it was mid-way through, and nothing else.
The common things that quietly make a service stateful:
In-memory sessions. The classic. A user logs in, session data lands in that process's memory, and the next request goes to a different instance and they are logged out. The fix is a shared session store or a signed token like a JWT that the client carries.
Uploaded files written to local disk. Works in development with one instance, fails immediately behind a load balancer, because the instance that serves the download is not the one that took the upload. Object storage is the answer.
In-memory caches holding authoritative data. A cache is fine when it is a copy of something durable and rebuildable. It is state when losing it loses information.
Scheduled jobs running in every instance. Scale to three and the nightly job runs three times. This needs a leader election, a distributed lock, or an external scheduler.
Long-lived in-process work. A request that kicks off a five-minute job in a background thread loses it when the instance is replaced. That belongs in a queue with a worker.
The honest counterpoint, because an interviewer may push: state has to live somewhere, and pushing it into a database makes the database the hard problem. That is a deliberate trade. Concentrating state in a small number of systems built for it, with replication and backups, is easier than having it smeared across every application instance. And some services are legitimately stateful: databases, message brokers, anything using consensus. Those get run differently, with stable identities and attached storage, which in Kubernetes is what a StatefulSet is for.
What interviewers probe next
"Are sticky sessions always wrong?" Not always, and they are usually a workaround. They are reasonable for a genuinely expensive per-connection setup, such as a websocket with large in-memory context, and even then a reconnect has to work.
"How do you handle a websocket connection, which is inherently stateful?" The connection is stateful and the application state should not be. Keep shared state external so any node can take over on reconnect, and accept that a node restart drops connections and clients must reconnect.
"Where does a JWT help and hurt?" It removes the session lookup, and it cannot be revoked before it expires. Short lifetimes with refresh tokens is the usual compromise, and a revocation list reintroduces the lookup you were avoiding.
Common mistakes
Reading stateless as "no state anywhere", then being unable to explain where it went.
Keeping sessions in memory and reaching for sticky sessions instead of fixing it.
Writing uploads to local disk, which works on one instance and fails on two.
Running a scheduled job inside every replica, so it fires once per instance.