Can you dye the costumes (Ezio's Costume, the Pirate Kidd Costume) and others or is the colour on them permanent?
Building on kotekzot answer:
The recolours are listed on the outfits section of the buy menu for the traders.
You can buy every recolour (outfit) and then go back and choose another one just buy pressing the button to select it (A button in xbox/pc with xbox controller).
This is the same behaviour as you find with the weapons on the trader menu!
I was actually expecting that these outfits would be selectable from the wardrobe in the secret room in the homestead. But no!