[The Might]

When Merry and Pippin were captured by Uruk-hai at Amon Hen on February 27, Grishnakh said the prisoners should be taken across the Anduin where a winged Nazgul waited. Ugluk taunted Grishnakh about the mount that had been shot out from under the Nazgul, and Grishnakh said that the winged Nazgul were not yet ready to show themselves on the west side of the Anduin. They were to be used for the War and other purposes.

I'll edit in the quote when I get home and have the books available for that purpose.

Idea is however, that Sauron somehow found these creatures somewhere, maybe the remains of some experiments made by Morgoth in the First Age, maybe found during his exile in the far east. He then proceededto feed them and to corrupt the race further in order to create the steeds. Finally, the Nazgul received them as steeds, but only once Sauron no longer saw reason for any secrecy. Horses were at first better because, as pointed above, they inspired less fear. But still, we know what by February 27 they still were not allowed to openly show themselves to the enemy.