Here on the Veldt walk into a random encounter, also make sure that you only
have three members in your party, if you have four then Gau won't come to
you. When you go into a random encounter win the battle and Gau will come at
the end and will travel with you now. After you are done head to the cave on
the southwestern part of the Veldt.
