Hey Leonard Richardson and Sam Ruby. I'm familiar with RESTful (at least how rails does it) /duck. Is a schema typically used when you do RESTful services? If not, what is the best way to make a RESTful service interoperable?
1. Interoperability between HTTP clients. Different clients should send the same HTTP requests to convey the same messages. The main problem here is that some clients are designed for simplicity and only support a subset of the HTTP methods (GET only, or GET and POST only). All the Java clients I've used (HttpURLConnection, HttpClient, and Restlet) support all the methods. HttpURLConnection is difficult to program to, though. For Ruby, I've hacked the standard library's open-uri to support methods other than GET, and made it available as the rest-open-uri gem.
2. Interoperability at the level of MIME type. Different clients should PUT and POST the same documents to convey the same state, and should interpret the server's response documents the same way. The information about how to do this for a given MIME type is in some definition document, which (for XML subtypes) usually includes a schema.
2a. When the MIME type is generic application/xml, interoperability at the schema level. Different clients should send documents in the same schema.
3. Interoperability on the level of workflow. Different clients should have the same knowledge about the capabilities of a resource, and about what links and forms "mean".
For a real-world example, see the 2007 interop event for the Atom Publishing Protocol (http://intertwingly.net/wiki/pie/April2007Interop). Look at the "X"es on the interop grid and you'll see a few common problems. These are at level 2 (improper client handling of relative URIs, server-side date parsing bugs, server rejects a document the client thinks is valid) and level 3 (client tries to use unsupported server features).
When you're serving or accepting documents of MIME type application/xml, a schema is useful. When you're serving JSON, you might use one of the JSON schema languages like kwalify. When you're serving XHTML with microformats, you can use META tags to link to XMDP descriptions of the microformats. The alternatives are to serve a more specific MIME type, or to describe the document format in natural language.
Schemas are not an unalloyed good. They can make it easier to write clients, but they also limit the ability of your service to change without breaking the clients. Sam might have more to say about this.