This quest is no longer required for access to The Poets Palace. However, it is still required if you wish to obtain the access quest for The Pedestal of Sky from the Djinn Master inside Poets Palace.
The locations for the pillow, mat, eggs, and chalice are random spawns in a specific area. See the talk page for a detailed list of possible spawns and photos.
Go to Maj'Dul and search for a red pillow that can spawn under any merchant tent.
Possible locations: ( 61, 140, -70 ) or ( -67, 149, -137 ) or (53, 139, 46) or (-176, 177, -93)
Trackable as "a red pillow"
Go to The Great Bonsai in the Pillars of Flame and search for a harvestable mat. ( 149, -189, -1623 ) Copy/waypoint 149, -189, -1623 or ( 308, -167, -1663 )
Go to The Seer Stone in the Pillars of Flame and search for harvestable eggs. ( 24, -45, -400 ) Copy/waypoint 23.83, -45.14, -399.69
If using a land mount, take the ramp at ( -43, -75, -622 ) Copy/waypoint -43, -75, -622 or ( -20, -93, -253 ) Copy/waypoint -20, -93, -253 in order to climb up to the cyclops area and then cross the path at ( -80, -46, -396 ) Copy/waypoint -80, -46, -396.
The eggs can even spawn on the ramps outside the immediate Seer Stone area.