Steve Maines attempts to answer the question "what is meant by 'hypermedia is the engine of state transfer'?" in a post on Subtle Distinctions, he thinks of this as "are your URI's really opaque to the client?".
I was surprised after Steve spent some time talking about URIs like "http://foo.com/CustomerProcessor.aspx?methodName=DeleteCustomer&customerId=12" that he didn't see more of the meaning of the hypermedia statement, so I'll try to help a bit.
Starting at the beginning of the sentence in question, hypermedia basically means documents with links, aka html with anchor or img tags. The most crucial point is that the links are a URI, in particular a string (not an XML structure) that has a bit of well-defined structure. The most important part of that well-defined structure is that the protocol is present, in much of the web case it is "http:". By necessity, the http protocol has the uniform interface, primarily HTTP GET and POST verbs. Because the verbs are limited and defined, clients know which verbs to use when interacting with the hypermedia. And that's the "engine of state transfer" part, which is that documents with links are how state is transferred.
Now let's imagine a web where some of these constraints are relaxed or changed. If we don't have hyperlinks, we might have xml structures. Which means performance is going to be *really bad* because your caching strategy is shot because defining canonicalization and then comparison algorithms for XML is *way* harder than the normalization and then comparision algorithm for a string. Just look at RFC's 2396 text for comparing URIs and then look at WS-Addressing's text for comparing EPRs. Oh wait, WS-Addressing didn't do any text for comparing EPRs. Ok, how about looking at XML Inclusive or Exclusive Canonicalization then.. Argh. The extensibility of XML is a horror for c14n.
Comparision is a real big plus for strings rather than structures. There's a lot of other reasons for strings, like human readability and usability. Putting XML structures on the sides of busses is just not going to result in network effects.
Documents containing links, aka hypermedia, is the unit of exchange. Now how are these units exchanged?
Let's imagine that there weren't constrained verbs. The client somehow has to know what "operation" to send to the identifier. In WS-* land, with many operations, the service author defines operations like "getStatus" and "getAddress" and "getShipper" etc. in WSDL. So the client needs the WSDL. And that WSDL isn't usable for any other application.
Putting the XML structure on the side of the bus isn't enough, the bus also needs the WSDL to know which operations to use including the inputs. I'm somehow thinking less network effect.
The web worked because there was ONE retrieval operation for all resources, HTTP GET. If an application like a browser gets a link, say from a person who saw the hypermedia application called a bus, then the app can count on being able to use that operation to transfer the state of the resource. If somebody puts a hypermedia link with "?message=DeleteCustomer" then a bunch of HTTP GETs on that resource may happen. Which is why it's generally wise to use GET to get things and other operations to DELETE things.
I could come up with a "better" constrained verb set, aka protocol. In my new groovey protocol, I'm going to define a "highfive" operation that retreives the state of an identifier. If my link structure clearly identifies the protocol, then clients can use the constrained verb set. So I can give out "davesgrooveyprotocol://pacificspirit.com/" identifier, and somebody can send "highfive" requests to pacificspirit.com. Now I just have to convince the world to use my new protocol. And that's the rub, is convincing people to deploy a new protocol. Which is why folks like me say "don't", instead we say "re-use URI schemes"
Now let's look at a web of connected hypermedia documents. Applications will retrieve a document. Based upon that document, they will probably do further interactions. Maybe they will create a new document, aka HTTP POST. They could even create a new hyperlink, such as a form that bindings form params into URIs. HTML says how new documents or URIs are created based upon forms. When a service returns an HTML FORM, it is saying it will follow the rules of that HTML hypermedia stuff when the client does it's HTML FORM thing. In the case of URI encoding for HTML FORMs, the HTML spec *IS* the "Relevant normative specifications ... that specify structured use of URI's or URI components" as said in TAG draft finding Metadata in URI
The opacity or non-opacity of the URI has nothing to do with "hypermedia as the engine of state transfer".
Strings for identifiers in documents with a defined protocol that supports a uniform interface is the essense of "hypermedia as the engine of state transfer". All those constraints are necessary to get the network effects of the Web. Relaxing any of the constraints would have crippled the web and we'd be in a much different world today.
Now I should restate that I'm not a believer in the "fullness" of REST. I think there is GET and then Everything Else. I've described why GET was essential for the web to succeed. On the non-read side of things, I believe that each type of update (include create, update, delete) is resource type dependent. There are going to be completely different side-effects and results from deleting a Purchase Order compared to a Book Order compared to a Centox Nerve gas Order. I described this as "why putFoo() is better than PUT Foo" and summarized in why Web services needs transfer protocols and specific protocols.