How were borders defined in medieval times? Like, how did you know when you crossed a border?
In general, borders were denoted by the presence of a toll booth which paid for the upkeep of the roads and security of the region. It was not common for individuals to be searched or questioned at these toll booths unless they looked particularly suspicious or during times of war, but the easiest identification to know one had entered a different region was the change in language, which was often quite distinctive.
In the Medieval period, travel and commerce was not particularly common, especially in the early period, which meant that languages could vary considerably even from village to village, which made it easy for travelers to tell when they had entered a new region.