As the title notes I'm trying to convert data into a shapefile using the REST service. The GeoData service has been made available for me to do that locally, but I'm unable to find any documentation on how to perform this. Can this service perform this and if so, how? Is there another service I should be using, instead?
Since you don't specify any development language, I'll provide a link to a tool by Jake Skinner:
http://www.arcgis.com/home/item.html?id=16e5cc64178941839eca62837f168ec9 ...which is based on python code.
To simplify it, you construct a REST query and the returned json can be loaded into a featureset.
Since you work with services there may be additional aspects to take car of: tokens for protected services, retrieving more features than a service is configured to return in a single request, etc...