You will find Terra in Mobliz, which is at the very tail end of the Serpent Trench. The Serpent Trench was underwater in the World of Balance, but now it is a very conspicuous serpent shaped continent in the World of Ruin. Terra will refuse to join the team twice, and each time results in the village being attacked by Phunbaba. Before meeting her, use a tent or sleep in the relic shop in the back of town to rest up. The path to fighting Phunbaba the first time should be straightforward. Terra will be annihilated in a one-on-one battle, and your party will come to her rescue. After you beat him, leave town and come back (again with full HP and MP, as the second fight will be more difficult).
Enter the building with the kids to learn about Katarin, then enter the far left building and follow the dog that entered the room to find a hidden stairway which leads to Terra and Katarin. By talking to them, you will trigger Phunbaba's second attack on the village.
Phunbaba is weak against poison/bio type spells, and has about 26000 HP. Fight him with your regular party for a while, then he will sneeze away two of your party members. Terra will join you in permanent Esper form until you beat him. Afterwards Terra will join your party and the sidequest is done.