After you escape from the Phantom Train, you continue on your way to Narshe.
Go south, then east, then go north. Go into the cave, enter the cave entrance, then go north until you are outside at Baren Falls. Before you go up to the north edge, unequip Shadow of everything, including relics, because he is about to leave.
Walk up to the edge, and Shadow will depart. Face the edge of the falls again, and you will jump. You will fight enemies on your way down. When you fight Rizopas/Rhizopas (a purple fish), have Sabin use Pummel/Clobber and have Cyan use SwdTech/Bushido 1.
After the Falls, there will be a cutscene where you meet a new character (default name: Gau). After Gau runs away, go south.
On the Veldt, you can encounter every monster and boss that I have numbered in this walkthrough. This will be more useful later.
If Gau appears after a fight, just hit him and he will run away. Go east in the Veldt until you see some mountains to the south. Go south until you are past those mountains, then go east, and finally northeast. The town of Mobliz is in the northeast part of the Veldt. Go into Mobliz, and be sure to buy Dried Meat in the item shop there.
Optional: Get Tintinabar/Tintinnabulum
In Mobliz, there is a way to get a Relic known as Tintinabar/Tintinnabulum. Anyone who equips Tintinabar/Tintinnabulum will regain a small amount of HP whenever he or she takes a step.
To get Tintinabar/Tintinnabulum, find the house that has an injured soldier inside. Talk to him, read him the letter, then go into the house with the bird in front of it, and pay the guy to send a letter for the soldier. Then go into the Relic Shop, talk to the Relic Shop owner (you don't have to buy anything) and go back out again, then go back into the injured soldier's house and another letter from Lola will be there. Repeat the process of reading a letter to the soldier, sending something to Lola for him, then going into the Relic Shop, then talking to the Relic Shop owner. Eventually the letters will stop coming. Talk to the injured soldier and he gives you the Tintinabar/Tintinnabulum Charm.
Now, if you bought Dried Meat in Mobliz, go back out onto the Veldt and fight monsters until Gau appears. Use the Dried Meat on him, and he will join your party. Kappa will explain how to use Gau's abilities. You can only learn Rages on the Veldt. The more monsters you fight outside of the Veldt, the more Rages Gau can learn on the Veldt. That is why there are numbered enemies on each page of this walkthrough: to tell you which enemies will appear on the Veldt after you fight them.
In short, Gau can use Leap in battle when you're on the Veldt, and he will temporarily leave the party. Keep fighting on the Veldt and he will eventually show up after a battle, having learned the Rages of the monsters fought when he leaped and returned. Don't hit Gau when he reappears. Just wait for the battle to end. If you accidentally hit Gau, you don't need to get more Dried Meat. Just fight more battles on the Veldt until Gau shows up again, and try not to hit him this time.
Take some time for Gau to learn some Rages.
When you are done learning Rages, go to the southeast part of the Veldt and enter the cave in the crescent-shaped mountain.
In the cave, go north and there will be a cutscene. Then go northwest, then go northeast when you can, until you see a wooden walkway. Walk along it, then go south afterward. You will reach Serpent Trench.