Welcome!
If I recall correctly, this actually is discussed in some of the classes. But there's nothing wrong with us examining it again (or separately).
I don't think we can prove it, but I think that the most reasonable theory is that Sam repeats a rumour from the Green Dragon to Gandalf without recognizing its significance.
First off, I think we can be confident that the message which reaches Gandalf is a vague rumour. As far as I can see, he never actually refers to it as a message. He simply says "I have heard something that has made me anxious and needs looking into" (Chapter 3). In fact, at the council of Elrond, he's even more vague about why he felt the need to leave Bag End. At that point, he reports his reasons in this way: "At the end of June I was in the Shire, but a cloud of anxiety was on my mind, and I rode to the southern borders of the little land; for I had a foreboding of some danger, still hidden from me but drawing near" (Book II, Chapter 2). The first comment seems to make it clear that he heard something, but it was so vague that a few months later he only remembers it as a general anxiety with no specific cause.
So, where could Gandalf have heard rumours?
I'm pretty confident that Gandalf hasn't been out gathering news himself. We're told that Gandalf "kept himself very quiet and did not go about by day, it was well known that he was ‘hiding up in the Bag End’" (Chapter 3). This seems to leave room for him to have been going out at night, but as he's telling Frodo that he's leaving, he also comments "I have been idle longer than I should" (Chapter 3), which I take to mean that he hasn't been doing much of anything.
If we accept that, then the only people he's likely to be talking to at Bag End are Frodo and Sam. I think that the news is less likely to come from Frodo for two reasons; First, he'd be more likely to recognize its significance and then Gandalf's reasons wouldn't be a mystery. Also, because I think Gandalf would say something to the effect of "The news you brought me has made me anxious" instead of "I have heard something that has made me anxious" (Chapter 3) if it came from Frodo.
So, Sam. And since we know Sam visits the Green Dragon, and we know rumours from outside the Shire also reach the Green Dragon ("One summer’s evening an astonishing piece of news reached the Ivy Bush and Green Dragon. Giants and other portents on the borders of the Shire were forgotten for more important matters" (Chapter 3)), it makes sense that he heard the rumours there.
We could probably come up with a reasonable theory for how the rumours got to the Green Dragon as well. It's pretty obvious that Hobbits within the Shire aren't shy about rumour-mongering. Once a rumour reaches the Shire, it's probably in every pub as quickly as a post-man can get his pony to the next town's pub for a pint. We also know that "There was trouble away in the South, and it seemed that the Men who had come up the Greenway were on the move, looking for lands where they could find some peace" (Chapter 9) and that those men made it as far as Bree. We also know that "There were probably many more Outsiders scattered about in the West of the World in those days than the people of the Shire imagined. Some, doubtless, were no better than tramps, ready to dig a hole in any bank and stay only as long as it suited them" (Chapter 9), and I suspect (from the fact that "Bucklanders kept their doors locked after dark") that these Outsider Hobbits came into the fringes of the Shire to share news (and cause mischief).
Knowing all of that, it's pretty easy to piece together a theory. The Black Riders are riding around randomly asking about the Shire. Some of the men who are fleeing North share the story of encountering the Black Riders in Bree -- mentioning that they're looking for the Shire and possibly including a mention of the Black Rider's dementor like effect on them. The fact that anyone from the South is looking for the Shire is news even to the Outsider Hobbits (some of whom, I assume, live on the outskirts of Bree much like they would on the outskirts of the Shire). The story spreads among the Outsiders, and reaches the Shire from them... and then spreads the normal way within the Shire. By the time it reaches the Green Dragon, it's probably garbled. But with enough detail left that when Sam repeats it to Gandalf, Gandalf gets the idea that someone is searching for the Shire and that there's some menace attached to these searchers. That's enough to make him set off to find the truth, but not enough for him to think Frodo should leave at once.
Obviously, I've built a house of cards here. We can't know the answer. But this explanation strikes me as reasonable... even if some of the details could be slightly different. If the answer isn't something similar to this, then the only other real answer I can think of it "Unexplained magic"... which is unsatisfying and dull -- at least, to me.