Ooh, ooh, I remember this one!

You get them from the soldiers on the ship from Junon to Costa del Sol(in the room with Sephiroth in it before the fight with Jenova).

Q:
Where do you get Cait Sith's Ultimate weapon?