Speak to the Sha'ir Messenger who wanders about Maj'Dul. She spawns twice a Norrath day (one of the times being 12:00AM, and the other seems to be 8:30PM - she has also been found at 8:00AM) at the Tower of the Moon.
Look for her on the mini-map.
It appears this is a triggered spawn; try zoning in from the Sinking Sands a few times and running straight for the Tower of the Moon ( -155, 177, -131 ) /waypoint -155, 177, -131, as that is where starts her path. She then patrols up past the arena ( -101, 167, 64 ) /waypoint -101, 167, 64 and finally to Champion's Court ( 29, 137, 187 ) /waypoint 29, 137, 187, where she despawns.
Attune the orb to four key places. These places are different for each character, chosen from a pool of locations listed below:
Climb a tall spire off the coast of the Pillars of Flame: ( 1574, -98, -64 ) /waypoint 1574, -98, -64 at the Djinn island.
Harpy's Nest in the Pillars of Flame: Up a climbable wall at ( 706, -96, -1229 ) /waypoint 706, -96, -1229.
Touch the orb to the earth at the foot of The Great Bonsai in the Pillars of Flame: ( 152, -190, -1670 ) /waypoint 152, -190, -1670
Immerse the orb in a small spring in the Pillars of Flame: ( 249, -108, -676 ) /waypoint 249, -108, -676 near the Sunstriders
Place the orb in a Blacksmith's Forge in the Pillars of Flame: ( 63, -86, -742 ) /waypoint 63, -86, -742 at the Swiftrider camp.
Note: this update can be a bit tricky; the back left corner of the forge (near the bucket) seems to be the only place to give an update. The blacksmiths forge update in Pillar of Flame can be gotten from standing on top of the forge I had to jump around a bit and it finally updated!
(Get off horse and actually climb onto Mender Grunthik's Forge from the front and it will update easily.)
After visiting all four locations, you receive your reward.