The Caladbolg is located in The Calm Lands, along a hidden path on the northern end of the plains. If you head there normally, then you will encounter a NPC who blocks the way and will not let you pass. To get him to move, then you will need to complete the entirety of the Chocobo Training exercises, up to and including Catcher Chocobo. You have to beat the trainer in the last one, but you don’t need to get under 0.00 seconds for the actual weapon. Once you’ve done all of that, the NPC will move out of the way, so head down and you should get a prompt that the [Celestial Mirror] is responding. Use it to get the weapon.
Note that if you leave the Calm Lands at all, the NPC will return to block your way. The only thing you have to do is start up any of the Chocobo Training exercises and finish it (no need to beat the time), which will cause the NPC to move.