Roy is on something of a crusade, pushing back on many publishers of HTTP interfaces who claim to be RESTful. I particularly like the latest: REST APIs Must be Hypertext Driven. Unfortunately the Word of Roy may be a little too divine for comprehension by many sinners, so at the risk of invoking the wrath of the posse, I'll try and simplify.

If you insist on using the word "REST" in association with your API, ensure you:

• Use URIs to Identify Things, and ensure the URIs make sense independently of how those things may be accessed.
• Don't bugger up standard protocols. You might think you have a better take on the authentication mouse trap, or an insight into how to make the Web transactional, but adding your own magic headers to HTTP and the chance is you're adding state beyond the URI. Above all, don't kill the bookmarking experience and testing with bog-standard, service-ignorant browsers.¹
• Expecting people to follow meta-data, instructions or documentation given out of band, in particular which URIs to GET, POST, PUT, DELETE, to or the content to POST isn't RESTful. It's much better to return links to other representations, or forms to update and otherwise interact with a resource ².
• A representation of a resource should contain links to other resources. Again, expecting people to follow instructions given out of band for templating URIs isn't RESTful ^3.
• Use widely understood and agreed upon representations, e.g. HTML, JSON and simple XML, and don't give different people different experiences of the same URI, that prevents exchanging bookmarks and kills many caching scenarios ⁴.
• You should be able to bookmark any page, exchange bookmarks and pickup where you left off. That is, the URIs should be cool, and shouldn't depend on cookies or other states. You shouldn't need a set of "click on this, then that, then the other" instructions to get to a page, a single bookmark must be enough.

Notes, or how The Web subverts REST:

1. It isn't a knife-edge, but often what differentiates meta-data from a form is a form is a document with links to actual resources, served as part of an interaction with a Web site, close in time before the interaction. It's a moot point if descriptions such WADL or WSDL are forms or meta-data, but most people would say the latter because they're often abstract, baked into software and don't give a human that click-through experience in a browser.
2. I suspect authentication tokens may be just about acceptable as external state, but only use a widely adopted scheme, usable in browsers such as OpenID and OAuth for delegation, though it's arguable exactly how RESTful these schemes are.
3. It's arguable that a HTML form with an action of GET is a way of templating URIs, and we all think that's fine - see note ¹.
4. Practically speaking, my experience of my profile page isn't always going to be your experience of my profile page. The state introduced by authentication changes that.

Of course some more puritanical souls like myself would question the use of the word "API", after all, The Best Web APIs are just Web Sites.