I'm pretty sure, that no matter which form of "news transmission" you pick, you'll always be tied to speed of typical horseback riding, if we're speaking about medieval Europe or a virtual, fantasy world with the same level and stage of development.
Whether it will be a diplomatic letters exchange, gossips traveling with traders or news brought by wandering mercenaries, it will always be able to travel no faster than riding a horse. Much often, slower. Simply, because people hadn't found a faster way of transportation at that times.
I think, we may assume, that a typical messenger, soldier, mercenary or trader can ride a horse for approximately ten consecutive hours (twelve hours or more or from dawn till dusk, but including few hours for horse and rider rest). This is the first factor (time), you can use in estimation for an answer to your question.
There are many sources (like this, this or this), that are trying to estimate how far can a typical horse travel. This, of course, highly depends on type of horse ride, whether you can change horses during one-day travel, what kind of horse do you have (how old it is) and what kind of terrain you're traveling etc., etc. A loose estimates from above mentioned answers seems to suggest, that you can expect from 20-30 miles per day for a leisure type of traveling or fast-moving travel in hilly terrain to 40-50+ miles per day in extreme fast travels, with changing horses, pushing them to limits and making very little or no rests.
Basing on these calculations, you may widely assume, that if city A is in distance of 100 miles from city B, news will need 3-5 days to reach.
These are very wide assumptions, that does not include other factors (how urgent message is -- from critical to gossip, if there will be immediate message spread or just by accident news spread etc. etc.). So, I think, you can use my answer just as a base for further research.
Ancient Persians
Edit (Nov 3 '14): As per Bobson's comment about Persian Royal Road: "Mounted couriers could travel 1677 miles (2699 km) in seven days". This gives us an hardly to belive (yet verified) value of 385 kilometers (239 miles) per one day of message travel in ancient Persia, 5 centuries before Christ and around 10-15 centuries before so called Middle Ages (depending on what point of Middle Ages history one thinks).
Ancient Egyptians
Edit (Sep 27 '15): Basing on information provided in "Pharaoh" book, by the Polish writer Bolesław Prus, message travelling from Wadi El Natrun (Google Maps, Wikipedia) to ancient Thebes (Google Maps, Wikipedia), that is on distance of 755 km / 470 miles, there and back (so 1510 km / 940 miles in total), would take 24 hours. Excluding just one hour for writing message and answer and exchanging messengers, that gives a hard to believe (in terms of ancient Egypt, around 1000 B.C.) speed of 65 km/h or 40 mph. There is absolutely no information on what kind of animal or other meaning of transportation ancient Egypt's messengers were using (I assume, they were using horses after all).
The same source few pages laters claims, that distance from mentioned Wadi El Natrun (Google Maps, Wikipedia) to ancient Memphis (Google Maps, Wikipedia), that is 151 km or 94 miles can be travelled on horse, by working trot within five hours.
Original question is about medieval Europe, about 1500-2000 years later than mentioned example. But since development of ancient Egypt was more or less equal to development of medieval Europe, I think we can skip that years difference.
And...
Edit (Dec 15 '15): ...there also are magical horses, since we're discussing the matter on Worldbuilding.se.