The GBAGE was a very good way of editing palettes, and I will still have the guide here, but updates to GBAGE have rendered an important tool unusable as it had cause errors in some cases. It is unknown whether it will be making a return in the future.
Alternatively there is a Hex method and if for whatever need you have to inflict harm on yourself and you really really wish to use a Hex method, I recommend finding a different guide by searching explicitly for the 'Hex Method' as I only have a truncated version, which is not really at all helpful.
Recommended APE Method:
Ok, so the first thing you want to do is download APE (Advanced Palette Editor). It can be found here.
Now what we will do first is find a Palette to Edit, lets use Eliwoods.
So let's open Nightmare and then open the FE7 Battle Palette Reference module. (I'm not sure if FE6 or FE8 have these)
Then we scroll through the list and find Eliwood's unpromoted palette offset.
Right we have that. So, now open APE, copy in FD9FAC (ignore the 0x8) and hit load, making sure the LZ77 compression box is ticked.
Now, if all we were doing was changing Eliwood's colours, we would be all set, simply copy the Palette down, change the colours and replace.
Simply use paint or Usenti to find RGB values.
** To be done: Further explain how to change the colours.
Repeat: If you are not changing the class of the character, or you know for sure that the classes both use the same palette order, then you are done here.
Now if you are changing class, I recommend using an already in-use palette of the class you want to change to.
Fore example: Lets make Eliwood a Cavalier.
First thing we need is the Palette of a cavalier. I'll use Sain's.
Put that in APE, load it and copy it. (ignore the random black splodge.)
The next thing you want to do is go back to Eliwood's Palette as that is what you are changing. So Reload his Palette.
After this you want to click replace. This replaces Eliwood's Palette but is not immediately visible, you must click load again to see the effects.
Great, so now Eliwood has the Palette of a Cavalier. It is at this point that you can use USenti or Paint to find out which colour is which spot on the sprite and edits can be made accordingly.
For now, I'm just going to make one of the greens purple, colour editing is done by double clicking the coloured bar in the changed Palette section.
Now we aren't done yet. First we must actually make Eliwood a Cavalier. Do this by going into the Chapter Unit Editor. (I recommend Blazer's Ultimate tutorial for further Information.)
And Finally, Enjoy you Eliwood who looks like Sain with Purple highlights.