If you waited for Shadow on the Floating Continent before jumping to the Airship, then you have to do the following to get Relm back.

Visit the Cave of the Veldt First

If you haven't already, visit the Cave on the Veldt to rescue Relm or Shadow. You won't be able to find Relm in Jidoor until you have found Relm or Shadow in the Cave of the Veldt. Also, be sure to leave Thamasa by the south exit. If you left by the west exit, go back into town and leave by the south exit instead. This is necessary to unlock the following quest.

Jidoor

Jidoor is in the middle of the southwest continent. Go to the big house in the north of Jidoor.

If nothing seems to be happening in the mansion, go back into Thamasa and be sure to leave Thamasa by the south exit. Then come back to the mansion.

Go north and walk up the stairs on the left. Read the book that appears. Be sure to read the entire book all the way through. Turn on the lamp at the foot of the stairs, then go up and check all the paintings. You will have to fight some monsters. Be sure to check the Emperor's painting twice for a clue about a star-shaped mountain range. After you fight the monster in the painting of the woman, a door will appear. Go through.

Go down the stairs, and check on the chair painting. Then go northwest and use the door on the left to find a chest. Then go back and use the door on the right.

In the next room, the doors will keep changing positions. Go north past those doors and go left to find a hidden chest. Then go back to the doors, and go through the left one when it opens. In the next room, go through the door on the left, then keep going north.

In the next room, if you walk under the floating chests, you will have to fight enemies. After each battle, you get an item. You can skip these battles by staying along the top wall. Check the middle painting to fight Still Life. It is weak to Fire. Go through the door that appears where the Still Life painting was.

Save at the save point, then go through the door on the right. Go north and talk to the person sitting on the floor. After a cutscene, you will fight Chadarnook/Chadnook.

Chadarnook/Chadnook

This boss consists of a Demon and a Goddess. Only attack the Demon; the Goddess will just come back if you kill her. The Demon is weak to Fire and Pearl/Holy. You might want to just defend during the times when the Goddess is there.

After you defeat Chadarnook/Chadnook, check the bookshelf to get an Esper. Then Relm will join you.

Esper Auction

Before you leave Jidoor, you can participate in the auctions to try to win a couple of Espers, if you did not win them before. Be sure to have at least 20000 GP before starting the auction, because that is the cost of Golem. Zoneseek/Zona Seeker, on the other hand, costs only 10000 GP. Go into the Auction House (north of the Item Shop) and talk to the guy standing inside of the Auction House to start the auction. There is a small chance (12.5%) that the item in the auction will be an Esper. There are two possible Espers that you can get here: Golem, and Zoneseek/Zona Seeker. If someone else wins the Esper, it will still be offered in future auctions. To start another auction, leave the building, then go back inside.