We're all calling these "hypermedia APIs" these days.
> with an associated client that actually uses it?
I have written a toy client here: https://gist.github.com/steveklabnik/2187514
You can run it against this site, written in node: http://alps-microblog.herokuapp.com/
Or this site, written in Rails: https://rstat.us/
It (should, I haven't tried it in a long while) work with both just fine. They both use the ALPS microblogging spec. yay generic clients!
As for people who have 'more real' ones: GitHub, Twilio (partially, more in the future), Balanced Payments (YC W11, iirc), Comcast (though that's internal :() Netflix has aspects, FoxyCart.
This year will be the year of examples.
Mike Amundsen's terribly named but amazingly well written 'Building Hypermedia APIs in HTML5 and Node' is a really thorough examination of this topic.
My experience has been that you can't communicate much through HATEOAS that's actually beneficial to a human programmer writing a client. Sure, you can add all the hypermedia links you want in your API responses, but how does that make writing a client easier? Wouldn't it just be helpful to crawlers?
Not trying to put down the idea - I want to believe, but I just haven't seen any obvious examples using it in the real world yet.