Stateless in HTTP terms means that each request has no knowledge of any prior request, i.e, there is no built-in mechanism in HTTP to track who is making requests and the effects of those requests.
In terms of RESTful services, it means that each request doesn't rely on state, e.g., saved client info, to fulfill a request -- all information needed to fulfill a request is enclosed in the request message (the CRUD operation, resource in question, auth tokens, app platform identification, etc.).
This means that your RESTful API should be guarded by a layered architecture that governs authentication, session management, and other non-RESTful operations.
In this context, both RESTful services and HTTP should operate under the same constraints: statelessness (as defined above).
It may seem intuitive to design a REST API like this, but you'd be surprised of the close-couplings found at the core of many REST services:
GET /users/:id
if authenticated and authorized //not stateless
send User resource
To combat this, most HTTP frameworks provide middleware layers.
Helpful REST-design questions: