Part I: Rescue Strago
To complete this sidequest you must first have completed Relm's sidequest and possibly the first part of Shadow's sidequest as well if you didn't save Shadow in the world of balance. Take Relm with you in your party to the Fanatics tower. For reference, the Fanatics tower is on the left side of the large U-shaped continent near the middle of the world map, and is in the middle of a mountain range in the middle of the left side of that giant U. Simply have your party talk to Strago and he'll join you. If you want to know how to defeat the fanatics tower see Final Fantasy VI/Fanatic's Tower
Part II: Defeat Hidon
To make the entrance to Hidon's cave in Ebot's rock available, you'll need to witness a sequence in Thamasa involving Strago and Relm. Head into Thamasa with both of them to witness a scene with Gungho. For reference, Thamasa is on the bottom right corner of the world map. Ebot's rock will appear after you complete the scene, on a little islet directly to the north of town. Pick Strago and any other three characters you would like. Traveling through Ebot's rock is mostly random, you'll step onto a teleporter and be zapped around from room to room. Pick up pieces of coral from treasure chests whenever you can and feed them to the talking treasure chest when you have enough. It will get dragged into the room behind it with Hidon and walk to the end of the room to see the big green monster himself.
Hidon will eventually cast GrandTrain, which is Strago's most powerful Lore, so it may be worth waiting to defeat him all the way until you receive that. Hidon is weak against fire and pearl and accompanied by a slew of Hidonites. Use your best multi-enemy attacks at first then your strongest fire spells or pearl, it should fall eventually.
If you miss learning the GrandTrain Lore or you wish to go back and steal some powerful equipment from Hidon or just earn some experience points, you can repeat the quest by just going to Thamasa and talking to Gungho until he says Hidon has appeared at Ebot's rock. Just go back and re-enter Ebot's rock and work your way up to Hidon again.