> But HATEOAS really isn’t about storing state in URLs.

I think saying they are unrelated isn't correct either. In order for hypermedia to be the engine of application state, the continuations of your application must be reified as URLs, ie. they must be stateful. This state could be stored server-side or in the URL, it doesn't matter, as URLs are only meaningful to the server that generated and interprets them.