The Moon Palace is filled with mostly nothing. It is simple to navigate.
If you fly Flammie over the big black circle, you will find out that you cannot land in the middle of it; in front of the Moon Palace. Instead, you will have to land near the border of it. Do so. Go north and enter Karon's ferry-a friendly Robin Foot brings you to the Moon Palace.
Karon will be waiting so you can go inside the palace. Avoid the Marmablues; they have a Magic Absorb spell. When you go through the door, you will arrive in a seemingly-empty, black, full-of-Marmablues area. There is a Crystal Orb in here. To find it, you will have to walk around until you stumble upon it. Or, from the entrance, head one screen up and go all the way left/right. Sylphid's Analyzer indicates that Lumina's magic will work. Let the girl cast Lucent Beam for the room to turn "normal". The next room is the stage room!
Head north and you will find an elemental. This time it is Luna, the moon elemental. Without hesitation, she bestows her powers upon both magic users.