When you publish an ArcGIS Server Map Service there is a tickbox in the service editor that gives more functionality to users consuming the services. ArcGIS Server 10.1 introduced the option to enable dynamic layers on a Map Service when you publish it. Don't worry if you forgot this option when you first published your services - you can edit your Map Service through ArcCatalog or ArcGIS Server Manager to enable it. You can read about enabling this setting here. This is the tickbox to look for:
If you are working with ArcGIS Online, support for this functionality was added in the March 2013 update. This is what you will see if you click on the drop down next to a layer in your map service when the box is not checked:
This is what you will see after ticking the box:
Notice that you can now set the visibility range on your layers, move layers up and down within your service, rename the layers, remove layers and change the symbology.
Please be aware there can be security implications when working with dynamic layers and workspaces. More information on these considerations can be found here.