I added california counties shapefile in ArcMap using add data option, I changed the color of counties using properties -> Symbology. I tried to export it to a shapefile using export data. It did create a shapefile and other supporting files, but it didn't save the coloring...whole map was same as my input shapefile with a single color.
How should I preserve the colors when I export it to a shapefile?
You can't preserve the colors unfortunately(as best as I know), whenever you bring in a shapefile, it automatically defaults to single value and a random color. If you are in the same map document, you can import the symbology from your other layer by going to Properties>Symbology>Import(towards upper right if I recall) and reference your symbology back to your earlier layer.
Another option is to save it a a layer (.lyr) file. Right click the layer in the table of contents, select Save as layer file, and save it where you want. This will preserve symbology. You can then add the layer file just like a shapefile, or use it for importing symbology as Ian suggests.
Technically, whenever you add a shapefile or feature class to a mxd, Arc actually makes a layer file out of it. Things like symbology, definition queries, etc., aren't stored with the actual data. I didn't know this until I talked with an ESRI instructor at a class, because it's not well documented. This is why Python scripts sometimes have to make a layer feature first.