I'm currently designing a REST Http api. (With HATEOAS stuff, to make clients "simpler", and avoid clients to do complicated things, instead of letting the api tell them what to do ...)
Because of the social characteristic of the app, in order to interact with the application, users need to be authenticated, and each user will have a slighty different "view" of the data. We'll take twitter as an example, it will be easier for everyone.
To authenticate users, we'll use OAuth, easy.
So, in the client (ios app...), a random user would maybe seeing a list of users should see:
John: Not Following
Rambo: Not Following
And another user would maybe see:
John: Not Following
To achieve this, the first solution would be for the client (in oauth term, the iphone/web/etc app), to get a list of all the users the authenticated user follow, and each time the client displays a list, compare each user with the list of followed users to know if it should display "Not Following" or "Following".
You should definitely embed the relationship in the user list response. It would be bad practice to force the clients calculate it.
This does not break the stateless contraint of REST as it's the interactions that are stateless, not the systems. The server will almost always have to store and maintain state. For instance the server will need to maintain state of who is following who.
Finally, I think you are not fully getting the "State" part of Hypermedia As The Engine Of ApplicationState. Basically, the resources are state machines. When you GET a resource, the valid state transitions are presented has hypermedia controls (links and forms) in the response. It's by following these links and submitting the forms that the client can change the state of these resources.
Including the description of the relationship type in the response body is not breaking the stateless constraint. The stateless constraint means that the web server can respond to the request without being dependent on any previous request (as has been mentioned by Tom, Jacob and kgb).
I'm not qualified to say whether what you're doing is a "best practice" or not, but in general Roy gave the following reasons for and against making your API stateless (see section 5.1.3 of his dissertation). Like many things in life there is a trade-off:
Problems with a Stateless System
Requests may need to be larger. Since data is not stored on the server between requests, each request may need include the same things over and over again.
In a stateless system, the server is dependent on the client maintaining the state correctly.
Benefits of a Stateless System
You know what a request is trying to achieve based solely on its content.
Improved scalability. Managing state between requests, particularly in a distributed environment can be quite complex. The first thing that comes to mind here is ASP.NET InProc session state, fine for a single server, single process instance, but it doesn't scale very well.
Also, according to Roy's definition of a resource I'd take issue with how I think you're defining your resources, with each user getting a slighty different "view" of the data. Roy defines a resource as a membership function that varies over time (see section 220.127.116.11 in the dissertation). The user list resource you've defined above varies by both time and by the Authorization header. Two different clients requesting /users at the same time would most likely end up with completely different results. This will make caching the results more difficult.
EDIT: Using the HTTP vary header would allow it to be cached.
From Roy Fieldings Architectural Styles and the Design of Network-based Software Architectures:
3.4.3 Client-Stateless-Server (CSS)
The client-stateless-server style derives from client-server with the additional
constraint that no session state is allowed on the server component.
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 kept entirely on the client.
So you embedding entity data directly in the response does not make your solution non-stateless.
On good practice:
It's a lot better to actually serve the user data than a list of numbers for the client to figure out what to do with.
However, depending on the amount of data for each user, you could consider giving a list of links to the user resource and state the "follow" relation as well. Then the client can fetch the details on the needed users. Which solution you choose should depend on what you believe the client will be needing, you might end up using several approaches.