Sauron got the majority of his information from Gollum, as is told in "The Hunt for the Ring" in Unfinished Tales:
Now Sauron had never paid heed to the "Halflings," even if he had heard of them, and he did not yet know where their land lay. From Gollum, even under pain, he could not get any clear account, both because Gollum indeed had no certain knowledge himself, and because what he knew he falsified [...] Thus it was that he dared to pretend that he believed that the land the Halflings was near to the places where he had once dwelt beside the banks of the Gladden.
As for how the Nazgûl knew to search for "Baggins", Bilbo himself told Gollum his name (Riddles in the Dark):
I am Mr. Bilbo Baggins. I have lost the dwarves and I have lost the wizard, and I don't know where I am.
Whether or not Bilbo had passed the Ring on seems irrelevant; even if he had (which he did) (and irrespective of who he may have passed it to), "Baggins" is still obviously the first person to search for; he could tell them where it had gone from there. Besides, Sauron himself would have known how difficult it was to pass on the Ring anyway.
Regarding a different surname, that indeed was the point of Gandalf's advice to Frodo in Shadow of the Past:
[...] you will have to go, and leave the name of Baggins behind you. That name will not be safe to have, outside the Shire or in the Wild. I will give you a travelling name now. When you go, go as Mr. Underhill.
So, all the evidence is that the only thing that Sauron and the Nazgûl knew was that the Ring had been taken by a Halfling named Bilbo Baggins. "The Hunt for the Ring" makes it clear that they didn't even know where the Shire was (it subsequently becomes clear that nor did they know its name), and outlines their search in the Vales of Anduin and along the Gladden, until they are eventually sent to Saruman (at this stage Sauron had heard of the prophecy in Gondor - "Seek for the sword that was broken..."):
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.
Following that the Nazgûl encounter Wormtongue who is the one who finally tells them where the Shire is (and its name):
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.
But even at this stage there is no reason to think that they have any name other than "Baggins", as their questioning of Farmer Maggot indicates:
"I come from yonder," he said, slow and stiff-like, pointing back west, over my fields, if you please. "Have you seen Baggins?"
