Yes, you can date Tifa, Aeris, Yuffie, and Barret. Almost every option in the game effects your 'emotional' levels with the other characters, and the decides who you go on the date with. Barret is obviously the hardest.

And dont worry about the Cait Sith prediction, it doesnt mean jack. You'll see how accurate he is later.