You can use Gimp, Photoshop, or Paint Shop Pro. Photoshop is obviously the best of those three.
You will need to download a .DDS plugin that allows you to open the Halo bitmap files in that graphics program. Search the
Utilities section of the Files Forum. Once it is downloaded, browse in your system to the graphics program, and drop the .DDS plugin into the plugins folder.
You will also need to download
Halo Map Tools 3.5. If the program fails to load, you will need to download
Microsoft's .NET Framework.
Once HMT is open, select "Open Map" at the bottom left. Browse to your Halo directory (C:\Program Files\Microsoft Games\Halo\MAPS [by default]) and select a map. When the map has loaded, select the [bitm]Bitmaps tag. Then pick the skin you'd like to edit. Click on the bitmap file, and click the "Save Bitmap" button to the right. Save the skin anywhere you'd like. Open the graphics program of your choice, and open up the skin file you just saved. If it asks to display MIPmaps, select No. Now edit it to your liking.
Once you've done that, it's time to save the skin. File>Save, and select the .DDS filetype from the dropdown list. Save the skin with Alpha 1, and click the "Generate MIPmaps" bubble. Save the file.
Back in HMT, select the bitmap file that you edited. On the right, click the "Inject Texture" button. Browse to the skin file you just saved, and click OK. If you did everything right, the edited skin should appear where the original skin just was. Click the "Save" button at the top of the screen (not "Save Meta"), close HMT, and run Halo. The new skin should appear ingame.