It is recommended that you do Shadow's sidequest before this one. If Shadow was on your airship at the End of the World, it won't be necessary, but if you just got on the airship as soon as you could and let Shadow die in the process, you will have to rescue Relm in a cave before doing this quest.
Head to Jidoor. For reference, Jidoor is on the left middle continent, north of Maranda and south of Zozo. Head to Owzer's house in the back of town. Flip the light switch at the end of the room and read the diary. Talk to the portrait of Emperor Gestahl twice to get a clue about the phoenix cave and the emperor's treasure. Then talk to the portrait of the lovely lady in the bottom left corner. Go through the door, and when you see two doors pick the left one for a moogle suit. Go into the next room with the constantly changing doors and walk behind it for a relic ring, and go through the very left door when it opens. Continue until you reach the room with the floating chests. Stand underneath them to trigger a fight. Talk to the middle painting when you're done in that room for another fight, which creates a door.
Head through the right door in the next room and you'll find yourself in a room with a painting with Owzer and Relm. You'll have to attack the painting itself which transitions between two forms (each with their own store of HP). They are both weak against Fire. When you defeat the Chardanook boss you'll win the Starlet esper and Relm will join your team.