Just thought I'd add that a lot of people are raising the issue of discoverability in restful services. From what I have read this is dealt with with three key constraints: mediatypes, link relations and HATEOAS (hypertext as the engine of application state).

Mediatypes provide a standardised way of processing the representations provided to and from a resource (HTML is processed in particular way, as is JSON, as are PNGs, etc). REST has a constraint that requires you use registered mediatypes. On the web, this is the IANA (http://www.iana.org/assignments/media-types/index.html). If you mint your own mediatypes and use them on the public web, they must be registered with IANA for a service to be considered RESTful.

Link Relations again provide a standardised way of manipulating resources. They describe how resources at the end of a link can be manipulated. Examples include the ATOM edit relation, others include the stylesheet relation.

HATEOAS is a constraint that demands that the the client application should move between states by processing the hyperlinks contained within a representation via the relations provided.

There are two things you should pick up from this: a general REST client will not be able to do much with a service without knowing how to process the mediatypes of the representations returned by resources, and will not be able to move between states on the client without understanding how to interact with the service via the relations the service uses. Think about the most common REST clients out there: web browsers. If I mint a new mediatype that represents "a visual representation of a kitten with a comical caption", I cannot realistically expect a web browser to understand how to process this. The knowledge of how to process my custom mediatype must be baked into the web browser, much like web browsers know how to process image/* media types.

Much the same problem exists with link relations. Most of the time Link Relations are defined with a mediatype (think how a web browser must move to the state of processing a stylesheet by understanding that the link rel "stylesheet" dictates that the user-agent must retrive the stylesheet resource by performing a HTTP GET on the linked resource).

RESTful client applications must be able to understand the mediatypes and link relations used in a RESTful web service.

These three separate constraints, constraints that must be adhered to to be considered RESTful allow a REST client to navigate a REST service. The beauty here is that the service may change the url space of a service at any point without breaking a client, as the client knows all it needs to know to safely move around the client application state, as the rest is provided by the service on a per request basis.

As others have pointed out, caching (another constraint) cuts down on the constant round trips that such a setup would suggest, but I'll leave that constraint for another commenter to flesh out :)

Finally, two points: HTTP headers are part of the representation. This means that mediatypes that may at first appear to violate the hypermedia constraint can be made into hypermedia representations via the link header (http://tools.ietf.org/html/draft-nottingham-http-link-header...). So PNGs can link to resources that contain metadata with a link relation such as "meta" (for example).

Second, many people mention the common HTTP verbs but ignore the OPTIONS verb. Calling OPTIONS on a resource can provide a lot of information back to the client about how they can interact with a resource. I've built systems that provide a list of HTTP verbs that a logged in user may perform on the resource, for example. Different users with different roles may be able to POST or DELETE, whilst others would see that they can only GET.

Hopefully this sheds some light on how RESTful services are made discoverable.