In many games that let you control a Empire or Kingdom, you can declare war on another one. However, the enemy will usually know instantly when you declare war. During the Medieval Times, how did Kingdoms and Empires know it was at war and how long did it usually take?

In the book War and the Law of Nations by Stephen Neff, he does go into the process of how the concept of a declaration of war developed.

According to Neff and his sources, war as a state of being (that is, the idea that a country is "at war" or "at peace") really only developed from Hugo Grotius' work in the early 17th century.

Prior to that, war was mostly defined by Cicero's definition of "A contending by force" rather than the more modern definition of "the condition of those contending by force." This is important for the concept of a declaration of war. The medieval concept of war was essentially individual acts or campaigns disrupting the normal state of peace, but not a dichotomy of peace vs war per se, as we view it now.

All of this is background, but it is important to understanding the rest.

A declaration of war itself primarily served to satisfy feudal notions of honor, as it relates to the just-war theory. In Warfare in Medieval Brabant, 1356-1406 by Sergio Boffa he states that these declarations of war, especially around the 14th century, tended to take the form of letters of defiance - essentially a letter delivered by a herald to the opposing head of state.

You also had the concept of reprisals - declarations of war associated with a response to something a belligerent country has done. A key point is that for general reprisals - in which the country itself mobilized - honor required a declaration of war, but specific reprisals (against, say, a single count that keeps leading raids across a boarder, or something similar) would not, because in this second case the action would be considered simply a response to the original belligerent (the raid-leading count) by the injured party (the other count he was raiding).

The specific time frames I found all seem to draw from Le droit de la guerre et les précurseurs de Grotius, by Ernest Nys. The idea was, to satisfy notions of honor, roughly three days was given between the declaration (dispatching the herald) and the first attack. Unfortunately, other works dated around the time of Nys' publication seem to claim that this practice was universal, which is patently false - it was only ever codified within the Holy Roman Empire after Frederick I, and with one particular french king, after all. However, the general consensus seems to be that - where it applied - the 3 day wait period was not so much to allow the other head of state to address the grievance, but rather that it was not honorable to attack an unaware opponent.

Now, given that pile of background information, this leads us to two possibilities:

The country declaring war actually sends a declaration of war/letter of defiance to the other party.
The country does not declare war, but simply mobilizes and attacks.

In situation one, the time it takes for the other kingdom/empire to know that you are at war happens to be as much time as it takes for a Herald to make it from one kingdom to another. Horse speed, though certainly not at full gallop. Other heralds within the first kingdom would issue a call to arms for vassals within the kingdom (per Nys again).

In situation two, kingdom 2 finds out that it is at war when word reaches them: they either get wind of kingdom 1's mobilization (that vassal call to arms) via information routes (not necessarily spies - this could simply be merchants moving through), or when first contact with the enemy is made. Declarations started to fall out of fashion by the 16th century - the Spanish Armada was sent against England without a formal declaration, for instance.

TL;DR: Assuming they sent out a declaration, it would go out as fast as the herald could make it from King A to King B at horse speed, but not a full gallop - mobilization for war could begin before the actual declaration, and as long as an attack did not happen until after, honor was satisfied. If they did not send out a proper declaration, the court would find out it was at war as soon as a messenger arrived from whichever boarder county/duchy got hit first, or when they got wind of the other country mobilizing against them.

Edit: I also want to state that if you are just looking for an idea of how ancient declarations of war were handled (rather than specifically medieval ones), Roman records were actually far more detailed on all of these subjects, and you can get a much more precise picture of what happened with declarations of war in Rome if you want from one of the Rome historians in this sub.