ShpEdit comes with the game - It allows you to export and import .bmp files (icons) into the .shp files.
To edit / create the actual icons use your favourite .bmp editor - or even Windows' Paint! The proviso is you MUST use the SPCAMO pallette or you will get wierd flashing in game as the smoke/water effects cycle.
There are a number of helpful guides here - Cross'
HERE is very good (its what gave me the confidence to try my own edits!).
Have fun and please feel free to ask questions if you have any problems.