If you find out, please tell me
I need to find out how, I'm hoping it doesn't involve too much hassle. I find that when trying to do something its always best to start with what is already available.
Try to read the existing leader heads, can you use flicster? or do you need a specailist program? To me it looks like they are all pcxs, at least those that you can change (civIII/art/leaderheads), you should just need to replace the relevant pcx (orbmp or what ever they are) with one of your own design. Don't change the name of the file, and then change the name in your scenario.
It is important that all the leaderheads are the same size, ratio and resolution.
Try taking the Abe lincon image, the happy one, and cutting and pasting your own art over him. then save the image as it is (that is same name, same palette, same location, same format) and see if that works. I'm real not sure if you can edit the flcs for the leader heads, who knows?