This can be done in ArcCatalog or the ArcGIS Server admin API, but I believe that there is a bug with making this change using ArcCatalog.
NIM085533: Changing the output directory for a service in ArcCatalog does not change the virtual directory of the service