the meaning of stateless

I don't understand how the word "stateless" is being used in REST.
Obviously POST and PUT create state on the server. Obviously, requests
after a state change depend on that state change (e.g. by using a URL that
was not valid before the state change).

I can almost live with this usage of "stateless" for persistent objects
stored on the server, because it can be thought of as not being "session
state": it lasts longer than a session. But in any moderately complex web
app, if you try to design a REST API you will quickly hit GET size limits
when doing complex queries. And then the suggestion is to do something like
POST the query parameters, returning a Location header for a "query" object
that can be fetched with GET. How is that not storing session data on the
server? How is that different from non-REST solutions?

There are three obvious differences between POSTing a query and just
generically using POST instead of GET. POSTing a query requires two
round-trips to the server, bad for latency. POSTing a query and using a
Location header limits the response to the creation of a single object,
which is fine for 1990's full-page-load design, but is unrealistic for any
moderately complex ajax app, where an API call will result in the creation
of multiple objects (e.g. creating related images). And POSTing a query
requires the tracking of large numbers of transient "query" objects, hugely
complicating both client and server, the very thing REST is supposed to
avoid.

Perhaps to clarify what is meant in REST by "stateless" someone could give
examples of things that *aren't* "stateless", and contrast them to REST.