The Excalibur (not to be confused with the Excalibur II) is a sword for Steiner that cannot be obtained until Disc 4, although you can do some of the parts for the side quest on prior discs. To officially begin the side quest on Disc 4, go to Daguerreo (requires either a flying Choco or the airship) and get to the second floor. On the far left side of this floor will be an Old Man, who when talked to, will ask you to retrieve an item called a Magical Fingertip. This item can be found at the Treno Auction House, but it won't appear immediately.
To get the Magical Fingertip to appear, you will need to win four specific items at the auction house, then sell those items to specific NPCs in Treno. The items you need, as well as the NPCs you have to sell the items to, are as follows:
- Griffin's Heart - Adventurer in Bishop House area
- Doga's Artifact - Scholar inside Synthesis Shop
- Une's Mirror - Nobleman in Bishop House area
- Rat Tail - Adventurer in Bishop House area (Disc 3)
Once you have sold all four items to their respective NPCs, head back to the auction house and the Magical Fingertip will finally be available. Note that this will likely set you back around 55,000 Gil, so make sure you have the cash on you. Win that item and bring it back to the Old Man in Daguerreo to be rewarded with the Excalibur.