After joining Gau on the Veldt, he tells you to go south to Crescent Mountain to find a treasure that will let you go to Narshe via Serpent Trench.

Serpent Trench

To get all the treasure, go right when asked. For the quickest way out, go left when asked.

When fighting Aspiks/Aspirans, don't hit Aspik/Aspiran with anything other than the Fight/Attack command. Otherwise, there is a chance that it will counter with Giga Volt. Gau can use the Rhinotaur/Rhintaur/Belmodar Rage or the Vaporite/Spritzer Rage, because these will make him absorb Giga Volt.

In one of the caves, if it seems like you have reached a dead end, look for a switch on the floor that you can step on.

When you wash up in Nikeah, go north to buy the best armor and weapons for everyone but Shadow. Also, stock up on items. Then go back down to the docks where you washed up, and talk to the guy on the boat to go to South Figaro.

After the boat ride, if you have completed all three scenarios, you will proceed to the cliffs of Narshe. If you have not completed all three scenarios, then you will have to proceed to either Terra's scenario or Locke's scenario.