If the Nazgul had access to the fell beasts - why did they ride on horseback to hunt the ring bearer?
I would guess that Sauron was trying at this point to keep things covert and re-acquire the One Ring by stealth rather than force. Sauron knew the Ring was in The Shire but not exactly where, and he didn't necessarily know that Gandalf had figured out that it was the One Ring.
A group of cloaked riders on a road wouldn't attract too much attention, but fell beasts flying across Middle Earth would most likely be noticed by all the peoples they flew over and would tip their hand to Sauron's intentions immediately (not to mention tipping off Saruman that there was Something Important in the West). IIRC the fell beasts only appear once a state of open war already exists and there's no longer any benefit in staying covert.
I've always assumed this was, as with other steps Sauron was taking, to avoid being too obvious. He wasn't quite ready to launch his (re-)conquest of Gondor and Anor yet, and didn't want his opponents to start acting against him yet.
Once the Nazgul returned for their new mounts war was clear, there was no need for subtlety.
It could also be that the new mounts were still pups when the Nazgul hit the road for the first time. It took time to grow them into the fearsome beasts that they became - and to house train them. (That's a litter box I wouldn't want to clean out.)
And the horses were working just fine until Rivendell. Maybe even Sauron needs to learn a thing or two: "Flying mounts! Of course! They won't drown!"
This is all described in the essay entitled The Hunt for the Ring published in Unfinished Tales. All supplied quotes are from that source.
At first the intention was indeed to be stealthy, because Sauron did not want the Wise (i.e the Elves and Istari) to know what he was up to:
Yet this weakness they had for Sauron's present purpose: so great was the terror that went with them (even invisible and unclad) that their coming forth might soon be perceived and their mission be guessed by the Wise.
From there they went invisible through Rohan, passed the Sarn Gebir and the Nazgul of Minas Morgul met up with the Nazgul of Dol Guldur.
This was (it is thought) about the seventeenth of July. Then they passed northward seeking for the Shire, the land of the Halflings.
The last point is important here: at this stage the Nazgul did not yet know where the Shire was.
From here they passed north up the Anduin and began searching, finding the old Stoor villages (presumably those formerly inhabited by Gollum's people) and their best guess at the time was that the Shire was somewhere near or even within Lórien:
They were told also by Khamûl that no dwelling of Halflings could be discovered in the Vales of Anduin, and that the villages of the Stoors by the Gladden had long been deserted. But the Lord of Morgul, seeing no better counsel, determined still to seek northward, hoping maybe to come upon Gollum as well as to discover the Shire. That this would prove to be not far from the hated land of Lórien seemed to him not unlikely, if it was not indeed within the fences of Galadriel. But the power of the White Ring he would not defy, nor enter yet into Lórien.
From here they continue searching north and finding nothing, until they meet messengers from Mordor; here we learn that Sauron had found out about the dream-prophecy in Gondor, Boromir's leaving, Saruman's deeds and capture of Gandalf. Now Sauron panics and orders the Nazgul to Isengard:
From these things he concluded indeed that neither Saruman nor any other of the Wise had possession yet of the Ring, but that Saruman at least knew where it might be hidden. Speed alone would now serve, and secrecy must be abandoned.
Yet again, they still don't know where the Shire is, but on the advice of Saruman (who did know but didn't tell them) they search Rohan for Gandalf, come across Wormtongue, and from him they finally learn the general direction it lies in:
Spare me! I speak as swiftly as I may. West through the Gap of Rohan yonder, and then north and a little west, until the next great river bars the way; the Greyflood it is called. Thence from the crossing at Tharbad the old road will lead you to the borders. 'The Shire,' they call it.
Finally some time past Tharbad they come across some fugitives and learn from one of them (who also turned out to be a servant of Saruman's) where it is:
One of them had been used much in the traffic between Isengard and the Shire, and though he had not himself been beyond the Southfarthing he had charts prepared by Saruman which clearly depicted and described the Shire.
This is the first point at which they actually know where the Shire is; they did not know before then and had to search the various lands they travelled through for it, and - of course - travelling back to Mordor to pick up some Fell-beasts at this late stage would just incur further delays.
So to summarise:
- At first they wanted to be stealthy.
- When Sauron learns what's going on he panics and they abandon stealth.
- And all this time they do not actually know where the Shire is until they are almost right at it's borders.
- Flying directly to the Shire is impossible because they don't know where it is.
- They needed to conduct a careful search on the ground, as well as waylay travellers and obtain information from them, both of which would have been difficult if not impossible if flying.
- The initial need for stealth was not abandoned until the Nazgul were far out of Mordor.
When Sauron first gained a hint of knowledge about the ring after torturing Gollum, he was as yet unsure of its authenticity. Gollum knew it to be his "precious" and a magic ring, and Sauron got all of this, but he was not sure if it was "The ONE". So he sent his trusted Nazgul on horses at first, to check if it really was the ONE. Gandalf had already found the ring's true nature and set Frodo to its safekeeping. But since he (Sauron) didn't know that the other side (Gandalf, Saruman) had gotten wind of it, he took a chance in sending them (Nazgul) on horses and not the winged steeds.
Later when the horses fell at the bridge of Rivendell, Sauron knew that it was the ONE. Speed had then become all the more necessary. Hence the Nazgul were clothed and given winged beasts to hunt the ring-bearer and find the Ring.
Gandalf says to Frodo just after he wakes up that the horses are dead, but that the Nazgul will be back with more terrifying mounts. It is likely that the horses were the Nazgul's transportation of choice until Gandalf sent them for a swim. Probably the plan was all along to raise these gigantic flying monsters into steeds for the Nine, but it seems to me that that plan was accelerated when the horses were killed. If this is true, then the flying mounts would still be young when they were brought into service, raising an interesting question: if Gandalf had not wiped out the horses, would the flying mounts have been mature and unstoppable, spelling doom for Frodo, Sam, and all of Middle Earth?
In the beginning of the tale, Sauron had already revealed himself to have manifested again. However, it was not known at this point that the Ring had been found and that he had a chance of recovering it. It could have even been assumed that he already had it back in his possession.
If he had stuck some Black Riders (whose only purpose in the story is to sniff out the Ring) on giant flying beasts, then people like Gandalf would have been immediately suspicious. That coupled with the impossibility of questioning people as they rode along ("Shiiiireee...Bagginssssss.") and you have a pretty good idea as to why they would start out on horses.
In The Two Towers, Legolas shoots down a winged Nazgul, at perhaps the first confirmed sighting of a winged steed by the Fellowship, so perhaps the time and the steed wasn't ripe, in addition to Sauron's desire for secrecy.
In the words of Ugluk (from "The Uruk-Hai" chapter of "The Two Towers"):
"...What's happened to your precious Nazgul? Has he had another mount shot under him? Now, if you'd brought him along, that might have been useful..."