Stateless means that the server does not store information about the client in between requests. Cookies, in the case of HTTP, are a way to keep HTTP stateless, but work around this restriction elegantly. The server does not need to store anything, and the client needs to send the cookies on every request in order to make the server know about certain aspects of the client (for example which token to use with an CIAM system).