There’s a lot of confusion about this, because most applications that call themselves REST don’t use hypermedia and aren’t REST at all.
Hypermedia is a generalization of hypertext for content other than HTML. You can say hypertext is a subset of hypermedia. Hypermedia can be HTML in a browser, with all links, buttons and everything that’s rendered so you can browse a website, or it can be a XML or JSON document intended to be parsed by an automated client who will also follow links and actions like a human would do with a browser, clicking rendered links and buttons.
HATEOAS means the interaction of a client with a REST application must be driven by hypermedia, or to put it simply, the client should obtain all URIs for every resource it needs by following links in the representation of resources themselves, not by relying on out-of-band information, like URI patterns given in documentation, as many APIs do.
This is simpler than it sounds. It just means that the interaction between a client and a REST application should be exactly like a human browsing a website. Take Stack Overflow itself for example. There are Users, Questions and Answers. When you want to see a list of your questions, you don’t go to a documentation website, get an URI template for listing your questions, fill a placeholder with your user id and paste it on your brownser. You simply click on a link to another document described as the list of questions, and you don’t even care about what the exact URI is. That’s what HATEOAS means in practice.
An hypermedia format defines the contract between client and server. It’s the hyperlink-enabled data format you are using for a particular representation of a resource in an hypermedia application. For instance, if you have a User resource, you have to document what exactly clients should expect from a representation of that resource and how to parse the representation to extract the information. Before interacting with your API, your clients need to implement a parser to extract the information, they need to know what properties the resource has and what they mean, what link relations they should expect and what state transitions are available, etc.
Hypermedia controls are the combinations of protocol methods and link relations in an hypermedia format that tells the client what state transitions are available and how to perform them. For instance, a Question might have a rel=post_answer link that expects an Answer representation as the payload of a POST method and will create a new Answer resource related to it.
Once you have a set of hypermedia formats defined, you need a domain specific media-type to determine exactly what hypermedia format is being used for a particular interaction. A generic media-type like application/xml only tells the client how to parse the data format, it doesn’t say anything about the information extracted by the parser. For instance, let’s say a document has the media-type application/vnd.mycompany.user.v1+xml, the client knows it’s a version 1.0 representation of the User resource in XML format. If you change the resource by adding or removing properties, links, etc, you can change the version number and clients won’t break, since they can request the version they were implemented for by using the Accept header. You can also provide multiple formats for the same resource, like XML or JSON, and even a pretty human-readable representation in HTML.
When you wrap everything together — the underlying protocol, HTTP; the contracts defined by hypermedia formats and media types — you have your Domain Application Protocol, which is the whole set of resources and available state transitions advertised by your application.
Needless to say, 99% of the so-called REST APIs you’ll find around the internet don’t follow all of this. Most of them are simply HTTP APIs that follow some of the REST constraints, sometimes because they don’t really need all of them, sometimes because that’s what the developers thought REST really is.