It depends on the type of Web client you are using.
If using the REST API then the web application can define a Colormap function to be applied on the server. see Raster Functions under
http://help.arcgis.com/en/arcgisserver/10.0/apis/rest/index.html
Some web applications based on Flex or Silverlight can apply color maps on images from image services.
If using a more simplistic / generic web app then you will need to apply the color map on the server.
If serving a single image the simplest method is to define the renderer in ArcMap then save it as a Layer (LYR) and publish this Layer as an image service.
If serving a large collection of such imagery create a Mosaic Dataset of them first. There are then two ways to apply the color map. Either as a property of each raster or as a property of the mosaic dataset. If the data is categorical or the color map is to change from image to image it is better to define the color map for each Raster. (See Batch Edit Raster Functions to apply to multiple rasters). If the 1 band images can first be mosaicked and then a the color map applied, it is easier to add the color map function as a property of the mosaic dataset. When using such color maps you should also consider what sampling method and compression to be used to access the data. If using categorical data then set the sampling to nearest and use PNG or LZW compression to access. If the data represents continuous image then use bilinear and JPEG compression for access.
I have the same problem: I can not use the Colourmap Function. It's always the error message saying: "the function could not be inserted.The input or output arguments are invalid." Can anybody help me with this? Thank you!