The Four Elemental Temples

Argul explains what he has discovered in the books:

Athas is as Athas is, but Athas has not always been that way. While the Sorcerer-Kings have done everything in their power to cover up what happened, they have not succeeded entirely. Rumors have been around for many years that Athas was once lush and green. That much is true, at least to a certain degree. I can tell you that now. However, for many years, it has been thought it was the defiling and the Cleansing Wars, where the Sorcerer-Kings destroyed race after race that ruined our once beautiful world. It appears that that was also a lie. The books do not tell me what did happen, but instead of a way to find out for sure.

It appears that there were four elemental temples. Fire, Earth, Water, Air and a last temple, called Nexus. Whoever they were, those that constructed them were hunted down and killed, but the secret of their location was preserved. The Four Elemental Temples hold directions and the key to the Nexus, which in turn holds the truth to what happened with Athas. 

The Tomb you found a little part of in Under-Tyr was neither. It was merely the tomb of the descendant of one of the original builders. From what I can gather, he was the last of his line, the secret dying with him. They used to be a whole organisation, protecting the secret of Athas, but paranoia crept in and destroyed them. It seems even fate sides with the Sorcerer-Kings.

Anyway, there are four elemental temples. Fire, Earth, Water and Air. Air is where the truth lies, but one has to pass through the other temples first, in order to access air. Why is unclear. Maybe it is to collect a key, maybe it is to do something else. I assume you should be able to figure it out once you get there.

Now, now, I don't want to argue about this. This is too important to haggle about. I know where the Fire Temple is, and roughly where the Earth and Water temples are. And no, I won't tell you that. If I have to trust you and send you out for the most important thing anyone has done in thousands of years, then you will have to trust me as well. I can tell you this much though. The Fire Temple is in the desert, probably buried by the shifting sands. The Earth Temple is in the Ringing Mountains, underground, and the Water temple is well, I will know once you have given me the last book. As for the Temple of Air, well that is for you guys to figure out.

With regards to the Fire Temple, it is mentioned in conjunction the Axxiniax Temple, a holy temple to the Ssurrans, a race of lizardmen who roam the deserts of Athas. Since the book also mentiones the Ssurrans as protectors of the Temple of Fire, it might stand to reason that they know where it is. Therefore, head out into the desert, to the holy temple of the Ssurrans and find some that know where the Temple of Fire is. Explore it, and find out what it is you need to know to enter the Temple of Air - then come back, and I will tell you were to go next.