I have read a lot of faux-REST APIs recently, which are essentially just HTTP/XML or HTTP/JSON remote services, and still need a client to be pre-built with specialist knowledge of URI structure. “Proper” REST allows a server to change its URIs however and whenever it likes, with client applications seamlessly adapting to the change.
InfoQ has published an excellent article describing an approach to building fully self-describing REST interfaces.
I still think more work is needed, though, particularly in the area of content types. The suggestion of application/blah.whatever+xml as per RFC 3023 is certainly better than an unadorned text/xml, but still does not provide the flexibility for client applications to sensibly handle new, yet similar, content types. In particular that proposal is limited to XML, with no equivalent for JSON or other data description formats.
Alternative approaches such as text/xml/blah/whatever might allow a more general support. In this example, transport and storage responsibilities might only care that it is essentially a textual format (something which is worryingly implicit in application/blah.whatever+xml), while parsing components might only care that it is text/xml, and so on. There is then the possibility for further information to be encoded in the content type. Consider a type such text/xml/link@href/whatever, which might indicate a textual format, parsable as XML, in which relationship URIs are indicated as a link element with an href attribute, and so on.
While compelling, such an approach could easily lead to fragility, though. Such a representation implies that the range of available content types is a strict single-inheritance tree ontology, with all the familiar problems
Definitely an area for further research.