Como você apontou, Roy Fielding escreveu um artigo interessante em seu blog. E este parágrafo resume muito bem "How to HATEOAS":
A REST API should spend almost all of its descriptive effort in defining the media type(s) used for representing resources and driving application state, or in defining extended relation names and/or hypertext-enabled mark-up for existing standard media types. Any effort spent describing what methods to use on what URIs of interest should be entirely defined within the scope of the processing rules for a media type (and, in most cases, already defined by existing media types). [Failure here implies that out-of-band information is driving interaction instead of hypertext.]
Então, sim, a HATEOAS depende de fornecer links para os clientes para direcioná-los ao aplicativo. Um exemplo típico é, como parte de um aplicativo bancário, uma conta bancária em que você tem um link para retirar e um outro link para fazer um depósito. Se seu saldo for negativo, o link para retirada desaparecerá. Isso é HATEOAS: você fornece links para ajudar o cliente.
Mas espere um minuto. No parágrafo citado, Fielding fala sobre descriptive effort , media type e out-of-band information ... interessante :-)!
Na verdade, a HATEOAS não está apenas fornecendo links, porque não é suficiente para um cliente ter apenas links sem sentido. Como o cliente deveria saber os verbos para invocar ao seguir um link? (GET / POST / PUT?) ... Como o cliente deveria saber os dados para passar como parâmetro ao seguir um link?
Se o cliente não souber essas informações, é simples: o seu cliente depende de out-of-band information (e isso é baaaaaad!)
Aí vem a parte interessante: como o cliente pode obter essa informação?
Resposta: através de self-descriptive message e media-type usado!
É assim que você faz HATEOAS: você totalmente (não apenas fornecendo links!) Direciona o cliente com links e mensagens auto-descritivas.
Dependendo do seu aplicativo, você pode ter que definir seu próprio tipo de mídia para descrever sua mensagem com precisão. Alguns outros existem, s eles são chamados de "formato hipermídia". HAL é um deles, mas tem algumas limitações. Uma comparação desatualizada pode ser encontrada aqui: link
Pessoalmente, sugiro que você dê uma olhada no Hydra, que provavelmente seria um padrão do W3C e tem muitos recursos. Por exemplo, você pode definir quais operações são possíveis em um link (= quais verbos usar, quais dados passar como parâmetro, se necessário ou não, etc ...). Algumas apresentações agradáveis podem ser encontradas lá: link
Para concluir: Eu diria que o HATEOAS está relacionado a legibilidade por máquina. Ao autodescrever a mensagem, você permite que qualquer máquina entenda sua API. Porque o legível humano pode envolver conhecimento fora de banda e isso é tipicamente o que não é RESTful (nem compatível com HATEOAS).