Am I missing something?

[Hookbill the Goomba]

I don't think so. But this from 'The Shadow of the Past' seems to answer how he found out:

Originally Posted by The Lord of the Rings, The Fellowship of the Ring, Chapter two: The Shadow of the past

"He hated Bilbo and cursed his name. What is more, he knew where he came from."
"But how did he find that out?" asked Frodo.
"Well, as for the name, Bilbo very foolishly told Gollum himself; and after that it would not be difficult to discover his country, once Gollum came out. Oh yes, he came out. His longing for The Ring proved stronger than his fear of Orcs, or even the light. After a year or two he left the Mountains.
...
"But from the snarls I even gathered that his padding feet had taken him at last to Esgaroth, and even to the streets of Dale, listening and peering. Well, news of the great events went far and wide in Wilderland, and many had heard Bilbo's name and where he came from. We made no secret of our journey to his home in the west. Gollum's sharp ears would soon learn what he wanted."

Hope that clears things up Master Morsul.