How to understand "RESTful API is stateless"?

Simply put: In REST applications, each request must contain all of the information necessary to be understood by the server, rather than be dependent on the server remembering prior requests.

Storing session state on the server violates the stateless constraint of the REST architecture. So the session state must be handled entirely by the client.

Keep reading for more details.

The session state

Traditional web applications use remote sessions. In this approach, the application state is kept entirely on the server. See the following quote from Roy T. Fielding's dissertation:

3.4.6 Remote Session (RS) The remote session style is a variant of client-server that attempts to minimize the complexity, or maximize the reuse, of the client components rather than the server component. Each client initiates a session on the server and then invokes a series of services on the server, finally exiting the session. Application state is kept entirely on the server. [...]

While this approach introduces some advantages, it reduces the scalability of the server:

The advantages of the remote session style are that it is easier to centrally maintain the interface at the server, reducing concerns about inconsistencies in deployed clients when functionality is extended, and improves efficiency if the interactions make use of extended session context on the server. The disadvantages are that it reduces scalability of the server, due to the stored application state, and reduces visibility of interactions, since a monitor would have to know the complete state of the server.

The stateless constraint

The REST architectural style is defined on the top of a set constraints that include statelessness of the server. According Fielding, the REST stateless constraint is defined as the following:

5.1.3 Stateless [...] each request from client to server must contain all of the information necessary to understand the request, and cannot take advantage of any stored context on the server. Session state is therefore kept entirely on the client. [...]

This constraint induces the properties of visibility, reliability, and scalability:

Visibility is improved because a monitoring system does not have to look beyond a single request datum in order to determine the full nature of the request. Reliability is improved because it eases the task of recovering from partial failures. Scalability is improved because not having to store state between requests allows the server component to quickly free resources, and further simplifies implementation because the server doesn't have to manage resource usage across requests.

Authentication and authorization

If the client requests protected resources that require authentication, every request must contain all necessary data to be properly authenticated/authorized. See this quote from the RFC 7235:

HTTP authentication is presumed to be stateless: all of the information necessary to authenticate a request MUST be provided in the request, rather than be dependent on the server remembering prior requests.

And authentication data should belong to the standard HTTP Authorization header. From the RFC 7235:

4.2. Authorization The Authorization header field allows a user agent to authenticate itself with an origin server -- usually, but not necessarily, after receiving a 401 (Unauthorized) response. Its value consists of credentials containing the authentication information of the user agent for the realm of the resource being requested. [...]

The name of this HTTP header is unfortunate because it carries authentication instead of authorization data.

For authentication, you could use the Basic HTTP Authentication scheme, which transmits credentials as username and password pairs, encoded using Base64:

Authorization: Basic <credentials>

If you don't want to send the username and password in each request, the username and password could be exchanged for a token (such as JWT) that is sent in each request. JWT can contain the username, an expiration date and any other metadata that may be relevant for your application:

Authorization: Bearer <token>

What might be wrong with your server

Once you have a session indentifier, I guess a HTTP session is being created somewhere in your application. It can be in your own code or in the code of the framework you are using.

In Java applications, you must ensure that the following methods are not getting invoked:

HttpServletRequest#getSession()

HttpServletRequest#getSession(boolean) with true

---