The answer to this question depends somewhat on the kingdom, geography, and era. The ancient Achamaemenid Empire of Persia (Iran) was arguably the first true empire in history, and spanned a sizeable amount of territory. It made use of regularly stationed outputs with stables always containing well-fed and well-rested horses, for messengers to quickly get around the empire. Combined with a primitive road system (which the Romans used to excellent military and economic advantage in their later empire), this ensured good communication and administration of the kingdom. Alexander the Great, having conquered Persia in the 4th century B.C., inherited this network of roads and indeed learned from the Persian method of government. In addition, the sub-division of an empire into smaller regions, run by local rulers or trusted generals, led to early top-down bureaucratic forms of rule that worked quite well. For Alexander the Great and the Macedonian Empire, these rulers were "satraps"; for Rome they were provincial governors.
In summary: the combination of regular stationed outposts (garrisons for the army, and trading/tax collection stations), and the pyramid-like sub-division of territories for administration by petty rulers and officials led to a, while often fragile, fairly efficient and manageable form of impirial administration that worked for the Persians, Macedonians, Romans, and later the Mongols.