Is there any reason given for how Gandalf the Grey becomes popular and is known by everybody in the Shire?
The Tale of Years records for TA 2758-9:
This was 11 years after the exploits of Bandobras ("Bullroarer") Took, which were still well-remembered in Bilbo's and Frodo's time, so Gandalf's assistance during the Long Winter would also be remembered.
This was also the first main interaction of Gandalf with the Shire, as we read in the Quest of Erebor (in Unfinished Tales):
The Hobbits got to know of Gandalf because he would hang out in the Shire and thereabouts smoking the Longbottom Leaf weed (I mean pipe tobacco). He's known as a wonderful conjuror and stage magician but his main reputation in the Shire is for his amazing firework displays. He's also known as a teller of fantastic stories about dragons and so on and is considered a bit of a disruptor of the peace.
There is a research, unfortunately only available in Russian, a carefully worked out conspiracy theory stating that whole story were told to Tolkien by some Elven Secret Service agent. And it turns out that there are two stories - a children's tale and a story of the Big Political Game between Sauron and Gandalf.
I doubt Google Translate could help it much, but anyway, here is one - it really worth to read.
There are many very interesting statements and conclusions, and the very first cite from the book is as follows:
And the following conclusion turns out to be quite obvious, if one think on the emphasized text. Bilbo's party weren't the first one. It was a successful one. And surely, the Ring was the only goal.
I seems Gandalf were organizing search parties on a regular basis, and hobbit member were necessary due to these folks' some unique features that make them best Ring keepers. And thus Gandalf were well-known in the Shire.
Edit: it seems I just did a grave mistake, by using wrong term at first. Although it is indeed a product of fandom, it is not a fiction at all, but rather a research paper, where the only fiction is citations from the book, to prove the author's statements.