You are right. HTTP is a stateless protocol, therefore REST inherits that quality too.
Here is the deal in simple words.
[REST client] -------> [API endpoint]
You have many REST clients, and you need to make sure that only authorized users will grant the access to your API endpoint. One solution as @James suggested is use a token mechanism such as JWT https://www.rfc-editor.org/rfc/rfc7519.
If you consider JWT authentication, the process flow will be as follows.
[REST client] -------> [AA service]-------> [API endpoint]
You will need an AA(Authorization, Authentication) service in the middle. For example in a microservices approach, this can be performed from a API gateway which is a gateway to all of your services.
Client will give AA service their username and password. In exchange AA service will give the client a JSON token signed only by the server so that the confidentiality is protected. This token contains 3 things.
Header which specifies the type of token and algorithms used to sign it
Payload which includes claims like to whom the token is issued, when should the token expire, what is issued user's role should be etc. (see https://www.rfc-editor.org/rfc/rfc7519#section-4)
Signature which a product of unsigned token signed by the server key
Then you encode each header, payload, signature with base64 and concatanate with a ".". You now have a JWT.
AA service returns this JWT in exchange for credentials.
Client should store this token securely (ex: local storage) and the communication medium should be encrypted(ex: TLS). See https://stormpath.com/blog/jwt-the-right-way#how-to-secure-jwt , https://www.rfc-editor.org/rfc/rfc7519#section-6
After that for every subsequent REST call, client should include the received token, preferably in the Authorization header although it is technically possible to send the token in the message payload as well.
Then it is AA service's responsibility to decrypt the token using its signing key evaluate claims in the JWT and act upon whether to authorize the API call send him HTTP 401,403 responses.