Hmm...unless I'm not remembering correctly, Ruby is supposed to show up automatically in disc 3(and after you beat Ultima on disc 2, if you do so). If Ruby's not showing up for you on disc 3, there's something wrong.

First question: are you SURE you killed Ultima? Not defeated, killed.

If not that, are you sure he's not showing up at all? Fly around Gold Saucer as low as you can.

If not THAT, I dunno.