Before you bother with gathering the Celestial Weapons and beating the crap out of some enemies with them (Omega Ruins, anyone?), you must begin by getting the Celestial Mirror. And, for that, you must first get the Cloudy Mirror - without it, this whole quest is meaningless. Begin by going to the Calm Lands and getting a Chocobo from the lady riding one around there. Then head to the southeastern portion of the area, just east of the entrance to Macalania - you should find a Chocobo feather on the ground there. Press X near it and you’ll flutter to Remiem Temple.
There, you’ll see two more Chocobos on the other side of the bridge. Examine the sphere near the left Chocobo, and then mount the Chocobo on the right. There will be a brief race in which you run along a series of platforms and get rewards based on the number of chests you open on the way. These extra rewards are relatively immaterial (although the 30 Wings to Discovery for 3 chests is insanely valuable) - the Cloudy Mirror will always end up being yours.
So, the Cloudy Mirror is yours now, eh? Problem is, it’s useless in its current state. Head to the entrance of Macalania Woods and speak with the woman nearby; it turns out her husband is missing. (Trust me, there’s a purpose to all of this.) Go east two areas from here to the four-way intersection and you’ll find him. Speak with him and return to the entrance to learn that their son is missing, too… See that sparkling path nearby? Follow it and go north/northwest when you reach the fork near the ambrosia-looking plant. Speak with the boy and you’ll be prompted to use the Cloudy Mirror, turning it into the Celestial Mirror.
Good, now we’re all set … except that we don’t have the Crests, Sigils, or Weapons.