You cannot change the map�??s appearance unless it�??s your own map service.
If it�??s your own �??Dynamic�?� map service (published using ArcGIS Server) you can change the look and feel using ArcMap , then restart service.
If it�??s your own �??Tiled�?� map service, edit the mxd/msd using ArcMAp, then recreate your tiles.
If it�??s an ESRI or another map service you did not create, you have to live with what they have published.
Drew
