Actual examples for HATEOAS (REST-architecture)

Netflix has a REST API based on HATEOAS that includes links as part of the resources.

Its not an implementation in the sense of running code, but I really like the article "How to GET a cup of coffee" on InfoQ. It describes the process of ordering a coffee at Starbucks as a RESTful protocol. This goes beyond the typical "everything is a resource" REST introductory article and focuses on HATEOAS. Highly recommended.

How about the Sun Cloud API? From the introduction:

The API presupposes no particular structure in the URI space. The starting point is a URI, supplied by the cloud service provider, which identifies the cloud itself. The cloud's representation contains URIs for the other resources in the cloud, and also for operations which may be performed upon them (for example deploying and starting virtual machines).

The backstory might also be helpful.