Suppose it's the year 53 BCE. I'm a legionary serving under Julius Caesar in Gaul. Crassus was just defeated at Carrhae. How would a messenger spread the word that he was defeated and killed? How long would it take news to spread from the political leaders to the far away legions and the average citizen?
It would take about a month for official letters to make it from one side of the Roman world to the other (for example, the Levant to Rome.) /u/fleetw16 is correct about this. What he is not right about is rumors and unofficial reports--this is before the era of phones, so news can only travel as fast as the fastest horse, which the official would have. For example, the truth of Antony's failed Parthian invasion took months to reach Octavian in Rome, while his official report had arrived earlier.
Source: Augustus, by Anthony Everitt
As a follow up question, how long did it take generally for roman citizens to find out that the (western) roman empire had fallen? I read years ago that for several years after the fall of Rome, there were (former) Roman citizens that still believed the Roman Empire was intact, but I can't find any source on that again (it might not have even been a legitimate source).