A remote system like a web service can hold state on behalf of a client. But because the HTTP protocol is connectionless the server can't automatically tell when the same client calls twice and when it should use some saved state. It's common for the client to identify itself with a unique token, and for the server to pull some saved state out of storage using the token as key. If this makes you think of HashTables or maybe even database tables, those will work.
There's a downside, naturally. Anything the server holds for you takes up memory or storage and time and effort of some kind to save and retrieve. This adds up with zillions of users. And if there are multiple servers behind a load balancer you need some way to guarantee you hit the same server or some way for servers to share state. It gets tricky in a hurry.
Ordinary web servers do exactly this kind of thing with Session objects of one kind or another. Your web service can use Session if it meets your requirements. Fancy servers like
EJB stateful session beans do this in much more robust ways.
For a simple flag like "has this client been authenticated" you can force the client to keep the state. Web servers send out cookies that the client sends back. With web services, your authentication service might return a token and require the client to send it along with subsequent calls. I think it's more common for web services to authenticate every call, tho.