> What exactly is the criteria of being a "hypermedia capable format"?
One document must be able to link to another.
> Is there a predefined way to deal with it in XML?
Yes, Xlink:
> In the earlier example, I had assumed he did exactly what you would do in JSON: make up a field for the purpose.
The problem with this is that it's non-standard and nothing understands it that isn't custom-written for that particular API.
> Though, honestly, that would seem to be the purpose of the "Link:" header.
Yes and no. Although the Link header is useful, it's not part of the document, it's a transport layer header. REST is transport-layer neutral.