The REST API is stateless, so you can t change the symbology via a connection to a RESTful service (although you could use a graphics layer to dynamically extract the features you want to display differently).

You ll have better luck using the SOAP API (via the Web ADF or simply connecting to the service via SOAP manually) and altering the symbology there. More information about this is available here: http://forums.esri.com/Thread.asp?c=158&f=2421&t=266974

As of version 2.0, feature layers existed in the ESRI JS API.

ESRI API samples show the use of renderers being used to change the default symbology for dynamic map services via feature layers through assigned unique value & class breaks renderers. As feature layers are derived from the graphics layer object, they render differently (client side vs. services on the fly img/tile export). Nevertheless, they do allow the alteration of a layers appearance based on developer defined fields/values.

Note the use of a unique value render on a dynamic map service in this:

example (code) http://help.arcgis.com/en/webapi/javascript/arcgis/jssamples/renderer_unique_value.html

live sample http://developers.arcgis.com/en/javascript/samples/renderer_unique_value/

var defaultSymbol = new esri.symbol.SimpleFillSymbol().setStyle(                                                                                                        
esri.symbol.SimpleFillSymbol.STYLE_NULL);
defaultSymbol.outline.setStyle(esri.symbol.SimpleLineSymbol.STYLE_NULL);

    //create renderer
    var renderer = new esri.renderer.UniqueValueRenderer(defaultSymbol, "SUB_REGION");

    //add symbol for each possible value
    renderer.addValue("Pacific", new esri.symbol.SimpleFillSymbol().setColor(new dojo.Color([255, 0, 0, 0.5])));
    renderer.addValue("Mtn", new esri.symbol.SimpleFillSymbol().setColor(new dojo.Color([0, 255, 0, 0.5])));
    renderer.addValue("N Eng", new esri.symbol.SimpleFillSymbol().setColor(new dojo.Color([0, 0, 255, 0.5])));
    renderer.addValue("S Atl", new esri.symbol.SimpleFillSymbol().setColor(new dojo.Color([255, 0, 255, 0.5])));
    renderer.addValue("Mid Atl", new esri.symbol.SimpleFillSymbol().setColor(new dojo.Color([255, 255, 255, 0.75])));
    renderer.addValue("E N Cen", new esri.symbol.SimpleFillSymbol().setColor(new dojo.Color([0, 255, 255, 0.5])));
    renderer.addValue("W N Cen", new esri.symbol.SimpleFillSymbol().setColor(new dojo.Color([255, 255, 0, 0.5])));
    renderer.addValue("E S Cen", new esri.symbol.SimpleFillSymbol().setColor(new dojo.Color([127, 127, 127, 0.5])));
    renderer.addValue("W S Cen", new esri.symbol.SimpleFillSymbol().setColor(new dojo.Color([0, 0, 0, 0.5])));

    var featureLayer = new esri.layers.FeatureLayer("http://sampleserver1.arcgisonline.com/ArcGIS/rest/services/Specialty/ESRI_StateCityHighway_USA/MapServer/1", {
      mode: esri.layers.FeatureLayer.MODE_ONDEMAND,
      outFields: ["SUB_REGION"]
    });

    featureLayer.setRenderer(renderer);
    map.addLayer(featureLayer);

If you want to change the appearance of the symbol in the map service its self then you need to either use the WebADF or create your own service that uses the SOAP API. The actual bit to change the symbol and then produce an image is quite easy, the hard part will be to then get open layers to consume it. I would either not bother or do as Michael suggests and bring back graphics to the client and draw them as you wish using OpenLayers, maybe have the layer set to invisible in the map service, so that they don t show up under the graphics.