How to change Chocobo's palette?

On the NPCs, do you have to change the sprite for every instance that a NPC shows up, or just the first time? For example, I have Vicks and Wedge with Palette 7. All soldiers are still palette 0, I think it is. Do I just find the first soldier that shows up and change his palette after 60 then whatever his sprite id is, or do I have to do it for every single soldier in the entire game?