Once you are onboard the Blue Narciss again, pilot it around the Outer Continent until you can see the sand in the distance. Get off in the beach and move towards the sand. The desert is located on the eastern side of the Outer Continent, so if you are having trouble finding it just continue piloting the Blue Narciss along the outside of the continent until you can see some prominent sand around the area. When you step on the sand you should be able to see four swirling holes of sand.
You can go to them and if you press x you will either have to fight an Antlion or you will be taken to Kuja’s Desert Palace. You do not want to have to battle an Antlion, they can be quite tough. Their Sandstorm attacks deals a large amount of damage to the entire party as well as inflicts the Darkness status ailment, causing your characters physical attacks to be less accurate. You may want to call Moguo the moogle and save your game before attempting to enter Kuja’s Palace, those Antlions could be brutal.
To determine which hole leads to Kuja’s Desert Palace, look into the center of each of them, a puff of sand sometimes spews out. Each time you see this it means that the hole in question contains a battle with an Antlion. Look for the one without a puff of sand and enter it to be taken to Kuja’s Palace. Zidane wakes up in a prison cell, you have no choice but to follow Kuja’s orders.
Head down the walkway until you reach the two Black Mages, they will send Zidane to Kuja. Kuja wants Zidane to bring him back the Gulug Stone from Oeilvert on the Forgotten Continent. The place doesn’t allow anyone to cast magic, Kuja allows you to select three other party members to go along with you. My party consisted of Zidane, Freya, Amarant and Quina. I always like to leave Steiner behind for this part. You can bring along anyone you like, but just make sure that you do not select a magic dependant character such as Vivi. Quina is just there to heal and s/he can learn some new Blue Magic abilities. Zidane, Freya and Amarant are going to be the damage dealers.
You will appear on the dock with your party members. You have to make your way to the Hilda Garde 1, the airship that will be taking you to Oeilvert. Make your way up the stairs to the right and head across the walkway. If you want you can stay here and have a few battles to raise your party member’s levels since the enemies are quite good in the exp department. Keep in mind that you don’t have the ability to heal your party members using magic at this time. Head down the stairs and head up the ramp to board the airship.
The ship sets out towards the Forgotten Continent, when it lands you will disembark automatically. You can’t get back on the airship, but if you approach it and press X, Zorn will sell you some healing items. Be sure to stock up on them. If you press select you can bring up the world map. Notice the white dot on the part of the map that is the Forgotten Continent, that is Oeilvert. Head towards that direction, you can have the mini-map up so you can see where you are headed. You can also train your characters around here if you want to, since there is an item shop on the airship you needn’t worry about running out of supplies.
Continue heading south, move through the canyon. Refer to the World map if you are having trouble finding your way. It is on the western side of the continent so make sure that you are moving to the south west, while you are moving through the canyon keep and eye out for any turns to the west. You should eventually have to pass through a spiral canyon that will lead you to Oeilvert. Remember that you can call the moogle on the world map to save your game or use a tent if you need to.