A web application, RESTful or not, is generally not simply a data service; it exposes various resources and provides some behavior, and so it has state; a distinction is made between resource state (client-independent, managed by the application), and application state, which is client-specific. A stateless application doesn't store (client-specific) application state; instead, it lets the client be responsible for it, and provides an API that makes it possible to transfer (application) state back and forth (thus "State Transfer" in REST). From the perspective of a client, a web application is a state machine, residing behind an API that allows for interaction, but part of the state is provided as contextual information by the clients, to supplement requests.
Now, while studying REST, You may have stumbled upon something called The Richardson Maturity Model - it describes the "maturity" of a web application API (evolving over the years), but it's useful to us as sort of reference that puts things in context. In this model, all of the maturity levels, except for the final one, essentially provide APIs that facilitate RPCs over HTTP. In this style of API design, HTTP is used as a transport mechanism, but the actual communication happens over custom protocols, so the interacting systems (clients and the application) rely on so called "out-of band information" to communicate (in this context, this just means that these systems communicate using some custom standard rather then leveraging hypertext/hypermedia and, say, the existing HTTP protocol). So what drives state transfer and state transitions ("the engine of application state") is not hypermedia in this case.
The final maturity level introduces the HATEOAS constraint, and only then the API becomes RESTful. The client initiates the interaction through the initial URI; the server responds with a suitable hypermedia-based representation of the application state (which may differ between devices, or clients, or due to various conditions - thus "Representational" in REST), which includes self-describing actions that let the client initiate the next state transition (so hypermedia is now what directly supports and drives application state).
Can I pick up on the statement that "Application State is client specific". That is how I understand it. [...] It has all to do with the server-side resource availability, nothing (apparent that I can see) to do with the client state...
Let me first make sure that we are on the same page. This is not client state (as in, the internal state of the client itself), but rather, the state of the web application that's particular to a specific client.
The example you mention doesn't really illustrate it well, but the list of links returned is essentially dynamically generated on the server and represents currently available state transitions, and as such, it encodes the current application state (for that particular client). Note that you may choose to transfer other bits of state-related information (in both directions) if your application requires it (so you are not limited to state transition metadata), but the constraint is to never remember any client-specific data on the server, because that hurts salability. Note also that this state doesn't have to be complete (doesn't have to be entirely meaningful when you look at it in isolation), but it has to be enough for the receiving party to make a decision and perform logic based on it and nothing else (so, no out-of-band information should be required, besides what's taken to be the common ground for the network (the standard protocols and data formats used)).
HATEOAS leverages the uniform interface (the common standards and data exchange formats) to decouple the clients and servers so that on the server side they can shuffle stuff around behind the "contract" defined by the hypermedia type, but also because communication based on out-of-band information (custom protocols) often doesn't leverage network infrastructure in a way that REST aims to do. (See the discussion below.)
In your example, the client wouldn't base its logic on the URI, but on metadata (or annotations), like the "rel" attribute. E.g., a browser doesn't care about the URIs in links, it just needs to know what kind of link it is (a clickable link, a form from which you can construct an URI, a stylesheet reference, etc.)
REST in Context
Unfortunately, REST has become a buzzword, and everybody is talking about how to be RESTful, but the entire context of REST is missing, and you cannot make sense of the REST architectural style without understanding this context (what is the problem that REST is actually trying to solve).
REST is a generalization of the architecture behind the Web. For most of us, the Web is a platform. But for people who developed REST, WWW is an application, which has a certain set of requirements, running on a world-wide network. So REST is meant for systems that are like the Web in some important respects, that need to satisfy a certain set of properties.
These are large-scale networked systems that are long-lived (think decades). These are systems that span organizational boundaries (e.g. collaborating companies), or boundaries between different subentities in a large organization (like different divisions, and even teams). Even though there's collaboration, the entities involved all largely operate (do work, and develop and deploy software) on their own terms, at their own pace, with their own security concerns, and they all use different devices, operating systems, etc. They need to access, and share references to, each-other's resources (documents, services, data), while being able to evolve independently and incrementally, without having to do extensive coordination (heck, it's hard to get people to do a coordinated deployment even within the same organization).
Those providing services need to be able to do things like evolve service versions, add nodes, or shuffle data around with minimal effect on clients. They need to scale. Clients (which may themselves be services) need to keep working despite of all this activity on the server side. The systems are likely to be used in unanticipated ways in the future. The resources they access and exchange may be of many different types, and realized (coded, typed, represented, structured) internally (by service providers) in many different ways, but even so, for the overall system/network, a consistent way to access resources and structure data and responses is required (uniform interface).
REST takes all this into account, and very much takes into consideration the properties of the network. It is meant to address the needs of applications that are, on a high level (within their own business domain), similar in terms of requirements and constraints to what's outlined above (or aspire to be).
And it does, but it's not a panacea. There are costs and trade-offs. It imposes a certain communication style, and there's a performance hit. You are always transferring data in a coarse-grained way, often the same data repeatedly, in a format that is generalized (and so may not be the most efficient for your service), with a bunch of metadata, often across intermediate network nodes (thus all the caching on the Web - it minimizes sending data back and forth, keeping the client away from the service when possible). User-perceived performance is important, which affects how you write clients (this is why browsers start rendering the page before everything is downloaded or ready). But you happily pay that cost to be able to build a system with the properties described above.
Conversely, if you are building a system that has different requirements/constraints, the cost may not be worth it.