I'm planning on making at the very least a promotions minimod, in which I change the value of most of the promotions, and add at least four new promotions. My question is how would I add the graphics for the new promotions? I'm quite rusty at modding, so I'd appreciate any help very much.

Assets/Art/Interface/buttons/Promotions is the folder.

They need to be .889x.889 inches .dds files, there is a photoshop template in the Assets/Art/Interface/Buttons folder if you need it.

Where are the leaders' graphics?

Inside the PAK they are in Art/Interface/Leaderheads. You'll need to go to the Downloads link (top bar) then Civ4 Utilities and download the FPK unpacker file to get at them.