You will now visit the world map for the first time. You can press the square button on the world map at anytime to call Moguo the moogle, who will allow you to save your game or use a Tent to heal your party. You now need to visit the Ice Cavern. While you are on the world map you can get into a few random encounters if you would like to so that your party can gain a couple of levels before heading into the Ice Cavern.
The Ice Cavern is very easy to find, it is located directly south of the exit from the Evil Forest. Head towards it and when you reach it before going inside head west and continue going until you reach a location marked as '?'. This is the North Gate, Melda Arch. Press the X button to enter the location. Once your party is done talking move over to the broken fence and open the two treasure chests to receive an ether and a potion. Leave this area and head back to the Ice Cavern entrance.
When you are in the area move up and above the platform that has a chest on it, hop down and open the chest to get a Tent. There are some pretty tough enemies in the Ice Cavern that can give you some trouble if you are at a lower level. At this point your party consists of Zidane, Vivi, Garnet and Steiner. Garnet is there to heal your party, you can press L1 or R1 to divide the healing amount between everyone in the party. Zidane and Steiner deal the physical damage, have Vivi cast his Fire spell on the Flans most of all. All of the enemies in this cavern are weak against fire so use this to your advantage.
Move up the screen and hop up the platforms and move into the next area. Move over to the right and head towards the steps that lead to a wall of ice. Press X to inspect it and Vivi will melt it using his magic. Open the chest that is found inside to receive an Ether. Before moving to the next area head around the trail leading behind the steps and open the chest to the left to obtain a potion. Once you are finished move up the screen and into the next area.
Move to the path on the left side and follow it and move down at the split. Move towards the chest that is elevated on a platform, climb up the piece of ice and open the chest to obtain a Potion. Head back down the piece of Ice and press the X button to examine it. Vivi will use his magic to knock it down so that it leads to the lower level. Move down and open the chest to receive a Mage Masher. Move back to the split in the paths and examine the Ice wall to have Vivi melt it with his spell. Open the chest to get an Elixir, then leave the area and head to the next one.
Move up the path and go towards the left. Press X in front of the Ice wall to have Vivi cast his spell to melt it. Follow the path that is now open to and open the chest to obtain a Leather Wrist. Move back and go to the right and open the chest to get a Phoenix Down. Once you are done leave this area through the top of the screen.
When you come to the fork in the road head to the left first. Approach the moogle that is frozen in the ice and examine the ice block to have Vivi melt it. Once he is free your view will switch to Mogster and he will teach you some about the card game, status effects and elemental properties. Once you are ready talk to Mois and save your game. You can use a tent also if your party needs healing, but the only one you need to worry about is Zidane for the next section.
Backtrack to the fork in the road and head through the path to the right. Make sure that Zidane is wearing all of his best equipment for this next area. Once you are sure that you are ready move towards the top of the screen and move into the next area. You will now have to fight a boss alone with only Zidane!
---Black Waltz No.1---
This battle could be tough, depending on what level Zidane is. Stealing is annoying for this battle, at the very least just go for the Mythril Dagger that the Sealion holds. Take out Black Waltz first since he has the least amount of health, and then go for the Sealion.
Zidane does take quite a bit of punishment during this battle, if Zidane is to ever achieve his Trance during, this battle instantly becomes very easy. If he does reach Trance, ignore stealing and just use Tidal Flame on the enemies, this should kill Black Waltz and leave the Sealion with a good chunk of health missing. You should be able to cast Tidal Flame twice, and the second time will kill the Sealion.
You should heal Zidane if his health goes below 120. The two bosses both cast Blizzard and the Sealion uses his physical attack 'Wing' to deal damage. Just physically attack them and switch it up with healing if it is needed until they are both dead.
Once the battle is over the Blizzard will have stopped and Zidane will go back to check on his party. Move back up and into the next area, follow the ramp and continue until you reach the exit. Go through it to return to the world map.