On the descending portion of the hype cycle now it seems that, like a guy in a "Rock Star" t-shirt, a "REST API" most likely isn't. It might be using HTTP as a uniform interface and identifying things with URIs, but then you find it provides text/xml or application/json responses with no links and out-of-band rules for teleporting (you can't call it traversing) to other parts of the API. Tight coupling like that is not what REST is about.
One that's getting very close is GeoServer's Configuration API. It has links from workspaces to datastores to layers, and a non-HTML client should in theory be able to follow them, changing the configuration state of the service in a step-by-step manner, led by the service itself, much in the same way you would through a web browser. All from one bookmarkable URI. This is what REST is about.
I say "in theory" because the GeoServer API doesn't hold water for formats other than HTML. Here's the problem: given a bookmarked URI ending in "workspaces" like http://example.com/workspaces, how does a client determine that this URI identifies a resource to which you can POST a new workspace and begin the configuration process using in-band information only? If you're working with a text/html representation of the resource, you'll be shown a form, and away you go, RESTfully. The semantics of forms, and specifically that submitting one sends data to certain URI, are defined in the text/html media type standard. A client doesn't need any out-of-band information: the form is in the representation, the semantics are specified by the standard "text/html" value of Content-Type header, both in-band. Now, if the server sends you back a text/xml response, there's no way for a client to know only from in-band information how it is to act on the response. That it's a certain type of resource (a GeoServer Workspace) because the URI ends in "workspaces" and the representation has a root <workspaces> element? That's out of band. That the bookmarked URI is a "GeoServer workspace bookmark"? That's out of band too.
AtomPub, on the other hand, holds water because the POST-ability of service resources (for creating new collections) is standardized under the media type "application/atomsvc+xml". If a client GETs a URI and that format comes back, the POST-ability is communicated, in-band. The "application/atom+xml" media type does the same for collections and entries, especially in its specification that an "edit" link tells the client via which resource it modifies entry and collection state. Standardizing on Atom and AtomPub, if you can, is therefore a good bet.
The interesting thing about REST that distinguishes itself from other styles is that interaction is driven by in-band information. Loose coupling, evolvability, and longevity are properties of a system that has the hypertext constraint. To get these properties, GeoServer and other APIs need to eliminate the out-of-band communication. Standardize on media types like HTML or Atom, mint their own media types (application/vnd.geoserver+xml or some such), or use links with standard relations in HTTP headers (aka Web Linking) and push for client support of those.