What is the preferred method of altering a layer's symbology dynamically? My web app consumes a map service via the REST API, but I don't mind using the SOAP API or ArcObjects (.NET).
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
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.