HOW.
Sorry, I couldn't resist

- Extract the desired .grp file from the "units\" dir of stardat.mpq or broodat.mpq
- Convert it with RetroGRP to a sequence of BMP files
- Edit them with a graphics program that preserves the palette (can't help you on that, sorry).
- Convert the frames back to a .grp with RetroGRP
- Create a blank MPQ with WinMPQ
- Import your modified .grp into this MPQ
- Rename it to match the name and path of the original file you extracted. The "\" is the virtual directory separator, and WinMPQ treats it as part of the filename.
- Compact the MPQ
- Fire up MPQDraft and create a self-executing patch of the MPQ
- Whenever you wish to have your unit graphic changed, run the .exe you created
You can also make the change a little more static by inserting your file into patch_rt.mpq, and the change will take place without you having to run an extra file. Just run Starcraft like you used to. Be sure to back up your patch_rt.mpq, just to be on the safe side.