How Saruman knew we are not told, to my knowledge, but he had the palantir and was in league with Sauron. In fact, the Ringwraiths were ordered theto stop by Isenguard and meet with Saruman, though this was after Saruman sent that message.
The Lord of Morgul therefore led his companions over Anduin, unclad and unmounted, and invisible to eyes, and yet a terror to all living things that they passed near. It was, maybe, on the first day of July that they went forth. They passed slowly and in stealth, through AnŏrienAnórien, and over the Entwade, and so into the Wold, and rumour of darkness and a dread of men knew not what went before them. They reached the west-shores of Anduin a little north of Sarn Gebir, as they had trysted; and there received horses and raiment that were secretly ferried over the River. This was (it is thought) about the seventeenth of July. Then they passed northward seeking for the Shire, the land of the Halflings.
About the twenty-second of July they met their companions, the NazgŭlNazgûl of Dol Guldur, in the Field of Celebrant. There they learned that Gollum had eluded both the Orcs that recaptured him, and the Elves that pursued them, and had vanished.2 They were told also by KhamŭlKhamû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ŏrienLó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 LorienLórien. Passing therefore between LŏrienLórien and the Mountains the Nine rode ever on into the North; and terror went before them and lingered behind them; but they did not find what they sought nor learn any news that availed them.
The NazgulNazgûl are ordered to steal over Anduin one by one and make enquiries. This is ordered soon after S[auron] learns that Gollum (who disappeared into the D[ead] Marshes) has been captured and is with Thranduil, and that Gandalf has visited that realm. Say sometime early in April. [...] At first the NazgulNazgûl investigate Anduin's Vale ... but can find no trace of Ring or 'Baggins' ... some begin to investigate Rohan.... Sauron is already in communication with Saruman [illegible] Palantir; but has not yet mastered him. Yet he reads enough of his mind to suspect (a) that he covets the Ring for himself and (b) that he knows something about it. The NazgulNazgûl are ordered to visit Saruman. Saruman is v[ery] frightened at S[auron]'s suspicion of himself and his knowledge of the Ring. Though he dislikes Gandalf intensely and is v[ery] jealous of him, he believes G[andalf] knows something vital about the Ring because the NazgulNazgûl [?ask] of the Shire which has always been a great concern of Gandalf, and because his agents have discovered that it is extraord[i-narily] closely guarded; also that Gandalf is now actually there since 12 April. He [Saruman] therefore thinks of getting his [Gandalf's] help... . The NazgulNazgûl, then, came to Isengard towards early? June. Saruman was helped at this point [by] g[ood] fortune. Radagast becomes aware that NazgulNazgûl are abroad in Anduin Vale spreading panic and searching for 'Shire'. He becomes v[ery] alarmed and can think of nothing but to go and consult Saruman head of order of Wizards. He does so ... not long after visit of the NazgulNazgûl to Isengard. Saruman knows that Radagast is a kinsman of Gandalf's and wholly trusted by him: he uses him as messenger, and sends him off to the Shire. Radagast leaves Isengard about June 15th. ...