Meet the mercenary 
Shadow near the Imperial camp.
Walkthrough
At the house near the Imperial camp, Shadow offers to join 
Sabin for free. He can help the group for part of this scenario, but may leave later; that temporary departure is separate from the much later decision about waiting for him.
In the camp, move through the tents and watch the Doma events. As 
Cyan, challenge the Imperial commander. After the poisoning, follow Cyan through the camp and help him escape with Sabin. Search cautiously because opening some containers can start fights.
Head south into the forest and follow its branching paths to the station. If you need recovery, use supplies before boarding; the next chapter begins on the Phantom Train.
Checkpoint
At the Imperial camp, explore the eastern and western tents before chasing Kefka through the scenes. A chest choice can start a battle with dogs; another chest contains a tougher enemy. After Cyan joins, speak to him repeatedly to move through the camp fights, then leave north in Magitek armor and head toward the Phantom Forest.