Supposedly, about 597, he was walking through Rome and came upon a slave market where some fair-skinned and blonde-haired children were being sold. He asked what they were and was told "Angli"; that is, they were Angles. His reply was Non Anglo, sed Angeli, meaning "Not Angles but Angels." Asking where they came from he was told "Angle-lond." He decided this "Angel-Land" needed to know all about Christianity, so he sent Augustine and a contingent of missionaries to England.
Furthermore, when told that their province was Deira and their king was Aella, he replied that they would be rescued de ira ("from wrath") and that Alleluia should be sung in that land.
This story is told by Bede in 732—the illustration above of the incident is from Westminster Cathedral—and whether it actually happened is up for debate. In the illustration you can see the monk Augustine standing to the right with a staff.
There is at least one other anecdote about Gregory involving wordplay. It recounts that Gregory wanted to go to England himself to spread Christianity. At a break in his journey, while reading his Bible, a locust startled him by landing on the edge of the book. He exclaimed locusta! and then thought it was a sign to loco sta, to "stay in your place/locus." As it happened, someone from the papal palace arrived an hour later to tell him he was needed back in Rome.
The Gregorian Mission to England by Augustine and company transformed the island. After Gregory's death he was referred to in Britain as "our Gregory," and the first biography of him was written at the monastery in Whitby. It was in England at the Synod of Whitby that customs such as the calculation of the date of Easter were made firm, and the Archbishop of Canterbury was one of the most powerful Christian offices after the pope. I'll summarize Augustine's spread across England tomorrow.