Explaining "state" in "Hypermedia as the Engine of Application State" (HATEOAS) is a bit tricky, particularly when you have to do it under two minutes.
The problem is that, the word "state" means different things to different people. For most of us coming from some background in web development, state usually involves numbers, strings, booleans, and other objects stored in some place, say, in an in-memory session. For instance, every beginner-level book on web development includes a shopping cart style sample that stores the cart in an in-memory session. If we extend that notion to understand or explain HATEOAS, it would make us jump to the conclusion that, to make hypermedia as the engine of application state, the server will have to encode similar objects into some XML or such form of representation in response to each request. This line of thinking is a trap.
Here is why. Once the server includes such state in a representation, the next step for the client is to replay the state in future requests to the server. Then we are talking about exchanging those objects back and forth, and not every HTTP verb has enough room to carry that state. This line of thinking will then start to shoot holes into the notion of a uniform interface because, to fit the state in a request, the client may have to resort to POST. I can almost see message passing over POST as the next logical step. At this stage, whoever is trying to explain HATEOAS may have make some lame excuses and move on. Whoever is listening will then conclude that "yeah, this won't work for my apps".
Here is an example that I find most useful to explain the "state" in HATEOAS.
There are three pages in a UI. The first page has a link to go to the second page. The second page has a link to go to the previous page as well as the third page. The third has a link to the second page and another link to the first page.
A client starts from the first page, and then through the link on that page, goes to the second page. The fact that this page has one link to the first page and another to the third page implies that the current state of the application (i.e. the interactions) is that "the client is viewing the second page". That is what it means by hypermedia as the engine of application state. It does not necessarily mean serializing application state, such as "
<page>2</page>" into representations.
I admit that I am simplifying this a bit. The point is that state does not necessarily mean some data stored in representations. HATEOAS means that representations reflect the current state of the app through links with known relations. Those links may contain opaque references to some persistent state on the server.