Well, he appears after you defeat Ultima Weapon. Are you sure you actually killed it? It runs off after awhile, you have to keep catching it and fighting it, until it eventually crashes near Cosmo Canyon.

Ruby Weapon appears after this, and his claw will stick out of the Corel Desert. You can use the Highwind or a Gold Chocobo to bump into him and initiate battle. It may be hard to see, it is kinda small. It's a little red thing, it moves around. Just run into it, and you'll get into a battle with Ruby. Hope it helps