Once you are on the Blue Narciss, pilot the ship towards the Outer Continent, move over to the western side and continue moving until you see a beach that you can disembark on. You should be able to see Conde Petie in the distance from this beach. Disembark on the beach and begin heading towards Black Mage Village, head around the hill until you see the forest, move through it and enter the village.

When your party steps foot in Black Mage Village, they will see that it appears to be deserted. Start of by heading straight, go into the door to the right and climb up the ladder behind the counter. Jump up onto the bed and hit the chest to retrieve a Black Belt. Once you are done exit the item shop and head to the left towards the cemetery. When you enter you will find Vivi and a Black Mage that stayed behind. Vivi runs off to see the others that stayed behind, follow him to the Chocobo house. Head back to the central area and move up to the right.

Vivi heads inside, follow him. After the scene Mr.288 will tell you about Kuja's secret palace, located in the desert. Leave the town and board the Blue Narciss once again.