http://en.wikipedia.org/wiki/Representational_State_Transfer...
Applying this to one of Vambenepe's examples of an AWS method--
"AWS mostly uses RPC over HTTP. You send HTTP GET requests, with instructions like ?Action=CreateKeyPair added in the URL..."
you can see that it's not RESTful. A RESTful version of this method would have something like "KeyPairs" in the URL path rather than in the query string, and it would use POST rather than GET to signify a create operation.
I think the best place to start from would be the Fielding dissertation: http://www.ics.uci.edu/~fielding/pubs/dissertation/rest_arch....
However, does it really make any practical difference whether the API makes full use of all the HTTP methods (GET, PUT, POST, DELETE)? Sure, it may be a bit of an abuse of the protocol to encode everything as a GET, but since you usually don't want any caching when using such an API, does it really matter?
In general, REST provides discoverability and interoperability that you don't get without a uniform interface.