When he is tortured in Mordor, Gollum famously screams 'Shire! Baggins!' to divulge the location of the Ring. However, I've recently been rereading The Hobbit, and at no point does Bilbo say the word 'Shire', or even insinuates it. I've heard some claim he remembers it from his youth, but that seems highly unlikely due to his lack of the memory of the word 'Baggins'. So, how did Gollum know?
Bilbo was apparently quite famous in certain parts of the world, in connection with the murder of Smaug. Merely listening for the name of a famous hobbit adventurer named Bilbo Baggins (in Dale) was enough to point Gollum in the right direction, and presumably to remind him of Bilbo's name.
'That is a sample of his talk. I don't suppose you want any more. I had weary days of it. But from hints dropped among the snarls I even gathered that his padding feet had taken him at last to Esgaroth, and even to the streets of Dale, listening secretly and peering. Well, the news of the great events went far and wide in Wilderland, and many had heard Bilbo's name and knew where he came from. We had made no secret of our return journey to his home in the West. Gollum's sharp ears would soon learn what he wanted.'
Fellowship of the Ring: The Shadow of the Past