You'll begin with control of Celes in the world of ruin. Your goal is to catch enough fish to either kill or revive Cid. The really fast moving fish are the ones you want, those are the yummy fish. In a pinch the normal moving fish will do, those are the regular fish. The really slow ones will make Cid even sicker. If you're not sure which fish is which, check your inventory, and save before completing the sequence. If you want to just get it over with and kill Cid, bring him the really slow moving fish, otherwise only go after the really fast ones. Eventually you'll be done and have a raft to leave the island somehow. You can travel to the west to reach Albrook, talk to the people there and see what's up, and you'll need to head North to find Sabin in Tzen.
Definitely save before you attempt this sequence. If you haven't done so already, purchase the esper from the guy hiding in the woods in the top right at dirt-cheap price. Kefka will fry one of the houses in town with the Light of Judgment, and Sabin will hold things up while you go in and take care of business. Make sure you have the sprint shoes equipped, and for your other relics you can pick either a black belt to make the battles go faster, a quartz charm to try to have fewer battles, or a relic (like a ribbon) to make you immune to stone attacks which would immobilize you and effectively annihilate you. The only treasures really worth having are a Magicite in the top right of the bottom floor and a drainer in the bottom left of the same area. However if you work really fast with a quartz charm or black belt you can nab all the chests and still escape. Sabin will join your party afterwards.
Head south then east to travel to a part of the world map where the path makes a giant U shape, head down the right side to reach Mobliz. Use Sabin's blitzes which attack multiple enemies to fend off the random encounters in the meantime. You can rest in the relic shop in the back of town, and walk down the stairs in another building to find Terra. She'll say she's lost her will to fight, and as you live she'll try to fight Phunbaba in a battle she's doomed to lose. Your party will take over, Phunbaba absorbs most magic and is weak against poison, so just keep hitting it with regular attacks and healing. You'll get an esper for your troubles and can go on your way.
Head back around the surfaced trench and north to Nikeah. Talk to the guards in the cafe and you'll run into Gerad outside who looks suspiciously like Edgar. Follow him on the ship to South Figaro and stock up on equipment while you're at it. While you're in South Figaro, you need to talk to Gerad, whom of which is in the inn, in order to advance. Otherwise, the turtle in the cave will not move to where you want it to, which may cause confusion. After that, you can head to the cave near South Figaro and go to the entrance to find a hidden path reachable by jumping on the turtle. You'll wind up in Figaro Castle, go down the stairs into the engine room.
Head down the stairs to where the path forks. Clear out the chests at the bottom and go in the left door for some more treasure. Walk down the center path and you'll finally be able to join Edgar in fighting a boss. Go into the north room and get a soul sabre from the statue. Work your way up and Figaro Castle will arise from the sand. Put Edgar at the front of the party and buy the new tool available as well as any items you may need. Have the man in the engine room take you to Kohligen. Go to the town and find Setzer in the bar, he'll rejoin your party.
If you want you can go North to the Colliseum for some fun. If you completed the sidequest with the soldier in Mobliz and performed well with the Emperor, you should have two Tintinabars which can be bet to win Experience Eggs which double your earned exp for a character. Equip a break blade and the battle should be easy, but save just in case. Most of the other fights will probably be too difficult at this point.
Head down the stairs and through the bottom left door. Get the treasure chest, go down the stairs and walk through the right wall in the next area to find an experience egg, make sure to equip it, it makes leveling up a lot easier. Get the chest at the bottom right door in the main room, and go up through the top right room to flip a switch raising the water level. Then go through the middle door in the main room. Jump on the turtle and read the tombstones in the lower room if you want, it just tells you the location of the exp egg if you solve the puzzle. Raise the water level and ride the other turtle into the next room. At the top left of the room is a monster in a box fight similar to the first whelk, don't attack the shell unless you use Celes's runic ability. Save and enter the main room for a boss fight against Dullahanan. Head north out of the room and you'll regain your airship.
From here you can go to fight Kefka's tower at any time although it's advisable to complete the sidequests first. The first thing that happens is a bird flying around which Celes asks you to follow, which will end up leading you to Cyan. You can either move on or tackle some of the sidequests now. Before you do anything else I'd recommend taking the airship to the beach where you hunted fish for Cid, you'll get the Palidor esper for free, it's best to do it now so you don't forget it.
Just as a general rule, you'll want as many experience eggs as possible. You can get them easily by betting Tintinabars or work your way up to Tintinabars by betting Elixirs and keep betting the next item you win until you get an experience egg. Also, the best monsters to fight to level up are Tyrannosaurs and Brachosaurs in Dinosaur Forest, an unusual forest north of the Veldt. Brachosaurs also drop economizers.
Also, save often and beware of flying, particular at low health, since you may run into a random aerial battle with DoomGaze.
One last thing to keep in mind about the sidequests is that the level of a character when he/she joins your party is set equal to the average level of the party, with the condition that it can't be lower than it was before. For most characters you'll need to level them up just to allow them to learn all the spells, but since Umaro and Gogo can't be taught any magic it might be worth waiting to have them join your party until you've leveled up sufficiently, unless you think you'd need their help sooner.