There are two questions here - they're both really good ones, and often overlooked by people who, as a result, massively misunderstand what governing the Roman Empire was like.

Part 1: How, and How Fast, Did News Travel?

Let's take the first one first - how quickly and reliably could a message travel from point to point (between centre and periphery, perhaps) in the Roman Empire?

In my previous life, I specialised in what are called Geographic Information Systems - essentially, computer programs that try to make sense of physical space and use it to understand the past. Stanford have recently come out with a fantastic application of GIS, which they call ORBIS - which is built to answer precisely this question. Let's plug a few scenarios in and see what happens:

1. Firstly - bringing the news of Caesar's death from Rome to newly-Roman Alexandria in good summer sailing weather. This is a direct sea journey - best case scenario, ORBIS reckons at sixteen days. In that time, you've covered 2683 km.
2. Getting that same news to what would soon be called Augusta Treverorum (Trier), roughly the point to which the German frontier had recently been pushed back, would seem to be simpler - after all, it's only 1464 km, just over half the distance. However, the lack of a good river route means that you've got to do most of the journey by road, and so it's likely to take 32 days if you go by foot. If you have access to a horse relay system like the Imperial post (see below), it might take as little as seven days.
3. If you've been sent to Alexandria but the weather's poor, and you can't sail across open sea, that has a major effect on the journey - it's now a trip of 3823 km that's going to take you at least 28 days.

There's plenty more playing around you can do, but I think this little exercise is enough to make a few general points:

1. Even in good conditions, this is not fast communication. A round trip from Rome to most of its major administrative centres was in the order of weeks or months, at the best of times - emperors simply could not respond in any sort of quick time to events. This in turn put a huge amount of initiative and power in the hands of the 'men on the spot'.
2. Water was by far the best method of travel - something well-known to military writers, who recommended transport by ship whenever possible. Indeed, for that journey to Augusta Treverorum, we took a boat up the Italian coast rather than using the best roads in the empire - if we could afford it, there was no contest. This in turn meant that it very much mattered where you were going - simple distance was not the most important factor.
3. As a corollary to the second point, chance and conditions played a huge role. The major Roman roads were substantial enough not to get washed out in bad weather, but that wouldn't be true of the smaller roads that you'd have to rely on going between towns and villages. Moreover, as we saw in the examples, bad weather or the wrong season could turn a mountain or sea crossing from something routine into an impossibility.

Beneath all this, there's another consideration - plenty could happen to ensure that the message never arrives at all, and there's at least some trading to be done between speed and reliability.

There was quite a bit of interest in the question of the imperial post among scholars of the first half of the 20th century. In a 1925 article, AM Ramsay noted that news could travel fast in a dire emergency and if conditions were favourable - that in AD 69, the emperor Galba, in Rome, received news of a mutiny in Germania Superior (around modern Mainz) in no more than nine days, which would ultimately bring down not his rule, but his successor's (it was a crazy year). However, he points out that the local governors were loyal, and that this route had good-quality, new roads and access to the military postal system, which would obviously be working flat-out to deliver such critical news. In other words, this was definitely not 'normal'.

Indeed, the Romans were very aware that communication could be difficult, and that this had major significance for how their empire could work. There's an anecdote, which I've failed to track down in the original, of an emperor (I think Caligula?) sending a message by ship to order a disgraced or disfavoured provincial governor to kill himself, but another ship arriving at practically the same time announcing that Caligula was dead. Figuring that the order was probably going to be forgotten in the transition, the governor wisely decided to ignore it. The anecdote does a good job of expressing both the potential difficulties of long-distance communication (logically speaking, one assumes that the first boat set out considerably earlier than the second, but must have been somehow delayed) and the Romans' awareness of how force majeure could impose limits on imperial power.

The imperial post may not, however, be the best way to think about the movement of news across the Roman world. People in the ancient Mediterranean moved around all the time - some of that migration was long-term, such as a military posting or joining a colonia, but much of it was cyclical, short-term and fairly short-range, such as seasonal migration into the city to work in the agricultural down season, sea trips to export and sell products, or trading missions and business ventures - in Caesar's time, a common trip would have been to Delos, to buy slaves being brought in from further East, then home to Italy to sell them, and he also talks about receiving information on Britain from merchants who traded out there, probably in gold, tin and perhaps slaves. These people naturally talked to each other, and this would be a major way of spreading news and gossip. As we'll see later, that had consequences.