The essential bit of information to know is that Excalibur is a re-forged version of the Legend sword Cecil obtained on Mt. Ordeals when he became a paladin. The in-game clue is obtained by exploring the Underworld, once you have an airship that can fly over the magma. If you take the airship to the extreme south east corner of the underworld you'll find a single town-like building on the map there. This is the home of the renowned blacksmith Kokkol. However Kokkol has gone into reclusion because he can no longer find the rare ore called adamant. Without having this metal, he cannot forge weapons of great strength and power. Therefore if you want him to start his smithy back up you'll need to find him some adamant ore. This will be your quest.

Obviously you need to know is when. You can start this quest after you drill out of the Underworld with the modified  airship Falcon. However you'll need to take all the skills you've acquired for going all different places on the Overworld into account to get to the places you'll be going. Indeed, you may already have obtained some of the things you'll need, however I'm going to assume you didn't, so just treat the following as a checklist if you have.

 

The first thing you need is the Legend sword. This is easy, you got it when Cecil became a paladin and since it cannot be sold or trashed then you should still have it.

 

The next thing you need is a Rat's Tail. The Rat's Tail is in a treasure chest in the Land of the Phantom Beasts, a dungeon / cave in the western magma sea of the Underworld. You may have found this already if you've cleared that dungeon and visited the village there. However if not, you'll need to do so. This dungeon contains a great deal of valuable items and equipment. The shops in the village there also sell valuable things. Furthermore it's well worth your while obtaining the Summons Leviathan and Asura. Therefore head to the Land of Phantom Beasts if you haven't already done so and find the Rat Tail.

 

Next, do you remember what you needed to do to get to the Cave of Eblan? If not, you needed to modify the airship Enterprise to be equipped with a crane to carry around the Damcyan hovercraft. Then you took the hovercraft to Eblan and used it to cross the shoals to get to the cave. You're going to need both of those, the airship and the hovercraft, for where you will go next.

 

Take Enterprise and the hovercraft to Silveria / Mythril Village in the eastern archipelago between Fabul and Mysidia. Just to the east of that island is another small island with some mountains and a cave entrance. You can't quite land an airship on the patch of green in front of the cave, however it is surrounded by shoals. If you drop the hovercraft on the Silveria / Mythril Village island and then land the airship and use the hovercraft to navigate the shoals, you can get to the cave entrance. This is Adamant Grotto.

 

In Adamant Grotto you will find two "mini" sized people, probably from Silveria / Mythril Village. One apparently is the other's son, and mentions that his dad found a strange ore and is a collector of rare animal tails. If you talk to the "dad" he will tell you he's found Adamant. If you give him your Rat Tail he will give you some of the ore. Do so and now you have what you need for Kokkol.

 

Return to Kokkol's and give him the adamant ore. Then ask him to reforge the Legend Sword. Once he completes the process, you will have the Excalibur sword. In addition, Kokkol reopens his shop and sells Shuriken and Fuma Shuriken which are excellent weapons for Edge's toss command, as well he makes Yoichi / Samurai Arrows which will be useful for Rosa.

As I mentioned this is one of the more powerful weapons in the game for paladin Cecil. I recommend taking the time to do this quest before proceeding into the Lunar Subterrane (final dungeon) for the first time. For you Advance players, it's probably best to do this before going to the Cave of Trial on Mt. Ordeals as well.

 

For you old-school players, the Excalibur sword was widely known as the best item to use with the old duplication trick. If you could duplicate large quantities of the sword, Edge could toss them for huge amounts of damage. Doing this made the final bosses of the game very easy. Therefore if you're playing an old Final Fantasy II SNES cart that might be something to think about. However the bug that allowed the duplication trick was corrected in later ports of the game, including the Advance version.