ArcGIS Server REST Admin

You can create a cache for a map service but it will not become available via the REST API until you clear the map cache via the REST admin page.

The REST Admin interface can be accessed via:
http://host:8399/arcgis/rest/admin/

Once the map cache has been cleared to check that the service recognizes it you should see:

Single Fused Map Cache: true

via the rest services directory e.g.
http://host:8399/arcgis/rest/services/myservicename/MapServer