Hypermedia, the forgotten aspect of REST

In a post to rest-discuss mailing list, Roy Fielding quizzed if anyone else know what was missing from the REST presentation slides made by Steve Bjorg.
Without looking at the slides and the following posts, can you guess what was missing?
If someone is going to give a presentation on REST, it is likely that they will emphasise the more popular aspects of REST: resource, resource identification, representation of the resource and the uniform methods for interacting and manipulating the resource.
Many presentations that I have seen would further concentrate on the look-and-feel of "REST-ful" URLs, giving the audiences the wrong message that REST is primarily about URL construction. Josh Sled brought a good example of how even a big-name (I'm not telling who, go figure it out from the look-and-feel of the URL) development group got REST wrong: http://developer.yahoo.com/photos/V3.0/createAlbum.html. Whatever do they mean by "Passed in as a REST parameter.", I wonder. Quick, the server ate too many REST parameters, pass in the non-REST ones.
What is missing is hypermedia. It's the last constraint mentioned in the dissertation. http://www.ics.uci.edu/~fielding/pubs/dissertation/rest_arch_style.htm section 5.1.5:

REST is defined by four interface constraints: identification of resources; manipulation of resources through representations; self-descriptive messages; and, hypermedia as the engine of application state.

But whatever does "hypermedia as the engine of application state" mean? I like Mark Baker's explanation:

Hypermedia as the engine of application state" is simply a long-winded way of saying that REST clients make progress via links embedded in the data they retrieve. That sounds like an almost information-free statement, but it's not difficult to violate this constraint, and it can be quite costly to do so as well.

For example, if you have a blog, and there is an entry for 2007-05-11, from your home page, there should be a link pointing to that entry. User and client should not be expected to guess how to get there.
Just as state is explicitly represented and transferred, so must the transitions.