Part I: Getting Cyan
This sidequest requires no party members beyond the default, but does require a bit of leveling up since you will need to fight through Zozo and Mount Zozo. You will also have the chance to fight the storm dragon, but it may be too hard for you to fight right now if you're just beginning the world of ruin. You may wish to choose to get Cyan and come back later, or to complete some other quests and level up first if you can stand being without Cyan for that long. Getting Sabin's Bum rush helps for fighting the thunder dragon in this quest, so you may want to compete Sabin's sidequest first.
At the end of the sequence getting the airship, you'll be directed to Maranda by a pigeon. Buy some equipment and you can talk to an old lady there who can show you the new location of familiar areas in the world of balance. You'll meet a girl there who's convinced she's still getting letters from Mobliz. Follow the pigeon she sends out to wind up in Zozo. Zozo is in the northeastern part of your current continent just for reference.
Walk to the north of town and talk to the merchant to buy some rust-rid, and walk through the cafe building, going out the right door and then trying the left door to use the rust-rid and enter Mount Zozo.
Do the usual routine of clearing out the chests, and you'll get some truly awesome equipment including the Aegis shield which is very effective at blocking magical attacks. Exit through the left cave for a gold hairpin then through the right one to move on. In the next room stepping on the switch unleashes the deadly thunder dragon from a chest, so save if you're sure you want to fight it. Exit through the bottom right to find Cyan. When you're done with him, return to the cliff to pick up a key to open the chest.
If you're determined to fight the dragon, equip two people with the thunder and aegis shields and step on the switch, and wait by the save point to fight it as it flies around. Use your most powerful bolt spells, heal often, and have Edgar and Sabin use the chain saw and bum rush respectively. It has 42000 HP but if you can survive its attacks it will go down eventually. Cyan will also give you a clue about Gau's whereabouts so you can do his sidequest next or whatever you'd like.
Part II: Cyan's Nightmares
This part requires having Cyan in your party, and I would recommend three other highly leveled up characters since they'll be doing all the fighting in Cyan's nightmares, you can empty Cyan's equipment for this reason as well. If you just completed Cyan's first quest I would recommend waiting to beat this one until you finished a few more sidequests and added more characters to your party.
To begin the quest, head to Doma Castle. For reference, Doma Castle is in the northeast area of the map, the castle on the small island between the giant U-shaped continent and the islands with the dinosaur forest and the Veldt. Head through the left door then the right door inside Doma Castle to rest in the beds there. The three dream stooges will try to dine on Cyan's soul, and you'll follow after them. You'll begin with control of whatever character occupied the fourth slot in your party. I'd recommend giving this spot to a stronger character who can hold his/her own weight until you find your other party members. Sabin is a good choice for his multi-enemy blitzes.
Save your game immediately. Some of the enemies have status effecting spells so you may want to equip a ribbon to protect yourself. When you reach the branch with three doors, head through the second one to regain your second party member. After going through the door in the area with your second party member, pick the top door to move on. Pick the right door out of the next set to find your third party member. In the next area heading through the right door sends you back to the start at the save point, and heading through the left door takes you to the exit where you'll fight the three dream stooges.
Curley is capable of reviving the other two members of the team so try to kill him first. They will do some annoying delta attacks which can turn party members to stone or do large damage so be prepared. Try some large multi-target spells to start with and do your most powerful physical attacks if you picked a character like Sabin.
You'll next find yourself on a nightmare version of the phantom train. In the second car flip the switch to be able to reach the first treasure chest which has a Genji Glove, and pick up the lump of metal at the end of the room to get the chest to hold still so you can get a flame shield. Flip the switch and remember the positions of the open and closed chests, which should just be the right one on the top row closed and the left and middle ones on the bottom row closed. The next puzzle is a little tricky to explain. You need to open up a path which will let you go through the bottom area by raising the two boxes at the bottom of the screen and rotating a platform. The first switch moves a platform which gives you access to another switch, you'll basically have to go back and forth until you work out a combination which lets you pass underneath the switches. Then enter the pattern we discussed earlier by closing the top right box and the bottom left and middle boxes and flip the switch to move on. You can save in one of the next cars, and go in the final one to find yourself transported to a new area.
You'll all find yourself in suits of magitek armor, running around the caves of Narshe. The bolt beam seems to do the most damage, use the heal beam if you need it and heal between battles. After going through the first area you can either go through the next area then turn around or turn around right away then go through the passage to move on. The doors in this area aren't "logical", you have to go backwards to reach a new area, otherwise you'll just end up running in circles. Follow Cyan over the bridge in the new area and you'll fall and find yourself in Doma castle.
Cyan's wife and son will inform you that you're inside Cyan's soul, where he's being tortured by a beast known as Wrexsoul. Save your game. You can go outside the castle and to the left and right to witness two scenes with Cyan and his son, and go in the top right room of the castle to witness a scene with his wife. When you're ready, head into the throne room and prepare to fight Wrexsoul.
The easy way to beat Wrexsoul is to just cast X-Zone from the start, which can be learned from the cursed ring or the Fenrir esper. Just have one party member cast it and he'll be defeated instantly. However, if you do this, you won't get the Guard Bracelet that Wrexsoul would drop if you did defeat him normally. At the beginning of the battle, he will "possess" one of your party members. This means that he only appears when that member dies. What you'll basically have to do is kill off a party member and see if his/her death triggers the arrival of Wrexsoul, and if not, revive that member and try another one. When Wrexsoul appears, use your strongest attacks on it directly, and when it disappears again, revive your party member and repeat the process for the other two. Eventually you'll defeat it, and Cyan will gain all of his swordtech techniques. Head back into the throne room for an Alexander esper, and make sure to get all the items in Doma Castle.