Gandalf had told Frodo that they should take the One Ring to Rivendell. He advised him to adopt the name "Mr. Underhill" when outside the Shire. He promised to return to Hobbiton in late September when they would leave. Gandalf then started for Isengard to seek advice from Saruman.
It was Mid-year's Day and on his way he heard disturbing news from Radagast. Believing that he might not be able to come back to Hobbiton in time, he came hastily to the Prancing Pony and wrote a letter to Frodo.
In that letter Gandalf said to Frodo that he might not return when promised and that Frodo should leave as soon as possible, preferably before August; when Gandalf would be available he would try to catch them up. If Frodo ever came to Bree he should trust Barliman Butterbur and leave a message for Gandalf. He also mentioned that Frodo might meet a Man named Strider (whom Gandalf had already met and informed on May 1).
He concluded the letter with 3 warnings: that he should not wear the Ring again, and do not travel in night; the a rhyme which would prove Strider's real identity, which is Aragorn; his worries that the forgetful Barliman might not send this letter in time. The letter was signed with the certh "G" for Gandalf.
Before leaving, Gandalf instructed Barliman to send this letter to Hobbiton as soon as possible. He also told him to expect a Mr. Underhill, whose real name was Baggins, giving his description. However Gandalf's worries proved to be correct. Not only he was captured in Orthanc, but Barliman also could not find someone who would travel to Hobbiton, and day after day, this obligation was forgotten.
Frodo never received the letter and kept on waiting for Gandalf. Having no sign from him, he departed on September 23, much later than Gandalf would have instructed him. Meanwhile Gandalf had escaped Orthanc and reached the Shire on Shadowfax less than a week after Frodo's departure.
It was not until "Mr. Underhill" came to the Prancing Pony with a company of 3 hobbits that Butterbur made the connection. Strider happened also to be there and both he and the hobbits tried to discern each other's trustfullness. Butterbur arrived with the letter which proved to Frodo that Strider was his friend.