The second quest of the [41] Necklace Recoveryωτϖ chain, after receiving it from Dran Droffers you'll have to return to Uldaman and seek out the Remains of a Paladin. The remains are located close to the beginning of the instance, on the northern side where the temple is split into four corridors (the paths with right angles) - it is in the latter half of this section.
As sure as Malton is a dummy, those gems are still in Uldaman somewhere. You're going to have to go back there and look for them.
Like I said before, if the information we have is correct then there's a ruby, a sapphire, and a topaz that go with the necklace. Find them and put them in the necklace.
As to where the gems are, who knows? Maybe you'll get lucky and find the corpse of the Paladin. If he's not been stripped clean already, then maybe he's got them on him still.
You seem to have found the remains of the paladin that Dran had mentioned from before. Searching the remains uncovers what would appear to be his journal. The book is in poor condition, as dried blood has stained most of the text in the book. What you can read, however, is gibberish; it is written in the native tongue of the humans, to the best of your knowledge.
You will need the book translated if you are to glean any knowledge from it.