After Locke and the Moogles rescue Terra from Narshe, you should go south to Figaro Castle.

Go to Figaro

In the overworld, go southwest to reach the desert. Figaro Castle is marked with a white spot in the world map. Go into Figaro Castle.

Go directly north until you find a guy sitting on a throne. Talk to him (default name: Edgar). After some dialogue, leave the throne room the way you came in. There are green rugs to the left and right of the door that you just came out of, and there are stairs north of each of those rugs. Go up either of those stairs to find a chest. Then go south again.

In this hallway, there are suits of armor. To the left and right of these, there are two doors (they look a bit like walls). Go into the one on the right to find some chests and a merchant who is selling tools for Edgar. Buy a NoiseBlaster and Bio Blaster there. Then go into the door on the left and open the chest there. You might want to get Tonics/Potions, Fenix Downs/Phoenix Downs, and other items from the merchant in this room.

Go south until you are outside, and use the bottom-left door. Go down the stairs and follow the path until you are outside, near a soldier riding a Chocobo. Go to the left and enter the small tower. Talk to the old woman to learn about Edgar's twin brother (default name: Sabin).

Now go back to the throne room and talk to Edgar. There will be a cutscene where Kefka shows up at the castle. After Kefka is in the castle, have Edgar talk to the two guards next to him, then to Kefka. After Kefka leaves, go up to the door at the top and talk to Locke. As Terra, follow Locke until you are outside of the castle, then go to the right and enter the tower. In the bedroom, talk to Locke.

After Edgar asks what Kefka is doing, go up and talk to the guard who is standing in front of the top door.

Flee Figaro

After a cutscene, some M-Tek Armors/Magitek Armors will attack.

Have Terra use her Fire spell. (There will be some dialogue during the battle if you have her use magic in the battle.) Have her use Heal if needed. Use Edgar's NoiseBlaster to confuse the M-Tek Armors/Magitek Armors, making them attack each other. After that, have Edgar use AutoCrossbow. Locke can steal Tonic/Potion from each M-Tek Armor/Magitek Armor.

After the battle, your next destination is the Returners' hideout.