You have to find every color variation for all characters. Here is a list in which mission you find one of the 4 colors for each character.
First Costume Color is in Tramont. Near the start of the level, hug the left hand side of the linear path till you find another small route leading off to the west. At the dead-end there you'll find a big mob of Horsemen and a Black Ghost.
Second Costume Color is in Colunei Canyon. You have to play the level wit Zazi and lower a brigde with her aimed crossbow shot. After beating the "Battle your way out" mission, enter through the doorway below the stairs and head eastward to the bridge leading to the easternmost point on the map; the bridge Zazi lowered back in her level will be down, allowing you the chance to cross to the other side and find a Black Ghost amongst the Swordsmen and Wizards.
Third Costume Color is in the Orphea Castle Interior. After surviving the "Defeat all wizards" bonus mission, you'll be able to kill a nearby Black Ghost.
First Costume Color is in Orphea Castle Dungeon. On your way towards the easternmost chain of Angel Statues you must rotate to open the final light seal, you will see a rolling boulder. Follow it up a series of stairs to a new area, dodging all the boulders in your path. Keep following the path and it will eventually terminate in an area with two Angel Statues. Use them to open the northernmost light seal door; inside is a horde of Harpies and a Black Ghost. Kill the Black Ghost.
Second Costume Color is in Holy Mountain. First, you must have played through the level as Zazi and you must have lowered the bridge that lets you reach the "Defeat the cavalry captain" mission. If so, the bridge will be lowered for Sephia when she plays the level; cross the bridge, destroy all the summoning towers and kill the enemies, then look for a small building nearby with a seal flame. Have Sephia destroy it and enter to find a Black Ghost inside.
Third Costume Color is in Twilight Wasteland. Before going into the bottommost field near the boss fight (where you have the last huge summoning tower battle), go north into the dead-end to find a big squadron of Ghosts. Hidden among them is a Black Ghost, however, there are reports that this one is glitched, specifically that the Costume Color sometimes does not get dropped. If you don't get it, try suiciding back to a checkpoint.
First Costume Color is in Tramont. After surviving the "Defeat the Ambushers" mission, kill that pesky Black Ghost that was firing shots from behind the forcefield
Second Costume Color is in Verdei Keep Defense. From where you do the "Rescue the allies" mission, look around south for a set of stairs leading down to a gate. The trigger crystal is behind the gate; shoot it to open the gate and head inside to find a room filled with crates and stone blocks. After collecting the Dark Reaper, a horde of enemies will appear in the room you are in, including a bunch of Ghosts. One of the Ghosts is a Black Ghost.
Third Costume Color is in Orphea Castle Interior. Right after beating "Destroy the summoning towers (2)", you will enter a circular room, and the next room after is a hall filled with Magic Cannons. As you enter the hall, look up and shoot a trigger crystal on a ledge to open a secret door in the circular room. Inside is a mob of Elite Ghosts and an Elite Wizard, summoning tower, and Harpies will attack from behind; in a dead-end next to the Elite Ghosts is a lurking Black Ghost.
First Costume Color is in Fort Seratem. You need to have played through this level as Galen first, and have smashed open the tower near the fleshy tentacle gantlet using Galen's unique ability. If so, the wall will still be smashed open when Levv plays the level; enter and drop down the shaft to find a Black Ghost wandering around down there.
Second Costume Color is in Fort Seratem Defense. One of the Ghosts in the "Escape the trap" bonus mission is a Black Ghost and drops the Costume Color.
Third Costume Color is in Orphea Caste Interior. Before you enter the throne room door that begins the boss battle, go directly right from it down the steps to find a group of Ghosts; one of them is a Black Ghost.
First Costume Color is in Forest of the Lost. After killing the enemy captain, go south and look for a slab Maggni can move aside to reveal a small secret area. Kill the Black Ghost lurking around there.
Second Costume Color is in Crystal Cave. You must have played through this level as Galen and you must have smashed all the symbol-covered rocks in what will be the eastern area of Maggni's version of this level. If so, as Maggni, go almost directly east of the giant block you push to access the north-easternmost escape route to find a small pushable block. Use it to jump to the nearby ledge and shove the large block up there aside to reveal a small corridor. If you smashed the right rocks as Galen, Maggni will be able to enter the corridor and find a Black Ghost inside a secret area.
Third Costume Color is in Colunei Canyon. You need to have beaten this level as Zazi. Once you do, progress to and beat the "Wipe out the Giant troops" mission. The route to the ruins will now be available, and the bridge Zazi lowered will still be down. Enter the ruins and head to the central area with the twin stairs to find a Black Ghost just sitting there. Beware, the ruins are crawling with Red Wizards who will flood the whole building with Giants and Red Giants unless you kill them first.