This answer is in regard to European rulers. Islamic rulers inherited a different set of cultural ideas about kingship, and I don't know enough about them to comment.

They were the rulers of their people, and thus exerted their rule over the places that their people inhabited. But they also made territorial claims based on blood right/inheritance, custom and history, or just the fact that they wanted more land. But, being king of a people or a realm doesn't necessarily mean that they actually had control over either. To understand this, let's take a step back, and look at sacral kingship.

Sacral kingship is the idea that the king is somehow sacred or holy. It is extremely widespread, existing in some form in almost all cultures. In Medieval Europe, this meant that the king was seen as an instrument of God, ordained by him to be above other men at the head of the kingdom. It's easy to think of this as the divine right of kings, but don't fall into that trap. Certainly it was the precursor to that. But the idea of divine right was much more absolute than the Medieval version. A really good account of medieval sacral kingship can be found in Francis Oakley's Empty Bottles of Gentilism: Kinship and the Divine in Late Antiquity and the Early Middle Ages (to 1050).^[1]

Medieval thought focused a lot on how the world was supposed to be ordered. Since people in the Middle Ages thought that God wanted kings to be at the top of the secular world, they believed that they needed a king. (There was a huge argument about whether the Pope was above the king, but that's for another day). This meant that, even when kings had no real power in a given area, the King was still their king. The king was so important, in fact, that their always had to be a king. Ernst Kantorowicz wrote a book called The King's Two Bodies: A Study in Mediaeval Polical Theology that explains this.^[2] Kantorowicz points out that when the king died, people said "The king is dead, long live the king!" This is because the moment that the physical body of the king died, the political body was transferred to the next rightful king.

Take, for example, the French kings. After the Carolingian Empire went into decline, the kings in the French part slowly lost more and more real control over their kingdom. Eventually, a new dynasty called the Capetians was established. The Capetians are called after the first king in the dynasty, Hugh Capet, who was from the Île-de-France. Hugh was elected king by a group of French nobles. Once the Capetians became the monarchs, the could start calling themselves Rex Francorum, that is the King of the Franks. However, that was about all that they could do. They had no power to tax anybody outside of their personal holdings in the Île-de-France, they couldn't muster an army from the great nobles outside the Île, they didn't administer any government except what they set up inside the Île, etc. Nonetheless, they were the kings of France. When Hugh's son Robert wanted to go on a pilgrimage/tour of France, he was able to, and hailed as king as he went to various religious sites in the country.^[3] But he couldn't do anything that we associate with powerful political leaders. Basically, everybody liked having a king, but nobody felt like the king needed to be in charge of them directly. Kingship was an idea.

You can see an example of this in Flanders after its count was murdered. The area was under a lot of political unrest. Theoretically, it was the King of France's job to choose the new count, but actually the king just "rubberstamped" whoever was going to become count anyway. But, Charles, the murdered count, had no heirs. The people of Flanders voluntarily turned to their King, who had had no actual political influence there up onto that point, because that was what custom dictate that they do.^[4]

Slowly, kings started being able to control more of the lands that they were theoretically kings of. They did this through a combination of canny marriages, military campaigns, PR, and implementation of the institutions that would become the basis of government. Eventually, the fact that the king was in charge of the kingdom became well established, and kingship evolved into the late medieval/early modern institution that aligns more closely to what people think of when they think of Medieval kings. Francis Oakley's The Mortgage of the Past: Reshaping the Ancient Political Inheritance (1050-1300) is a good survey of this development.^[5] And hopefully his final volume will be out soon, which will bring us to the 17th century.

This is a bit tricky. The Roman state saw itself as universal (in its rhetorics at least), so technically the Roman Emperor was sovereign over the world. Near East despots had similar attitudes, and we see the same also in steppe rulers like the Mongols. Germanic rulers on the other hand are often little more than military leaders of an army. When those two ideas meet and a mere Germanic general can be equivalent in power to the Emperor, they start to become very muddy. When Charlemagne thus claims the title of Emperor (opposed to the Eastern Roman one), he shifts emphasis again (which is also coupled with a number of expansionist military campaigns). However, when his empire is divided up between the sons of Louis the Pious, territoriality wins out as the Frankish 'tribe' (or more accurately the state, by now) is split up, and the sovereignty of the three rulers is defined by territory, as lines on the map, in the treaty of Verdun. I think this is the turning point when kingdoms are defined territorially, though some vestiges of tribal rule remain (in legal jurisdiction, for example).

During the Norman period, at least, kings in western Europe were mainly named in their official documents as rulers of a people. William the Conqueror, as you mention, was 'dux normannorum' (duke of the Normans). I don't have anything handy with which to check how he was styled during his reign in England but I thought it was 'rex anglorum'. I could be mistaken on that. If he is 'rex angliae' it's an uncommon example.

Another uncommon example, of which I'm much more certain, occurs in Sicily while it's under Norman rule. The Hautevilles who established themselves as kings of Sicily are styled as exactly that in their Latin diplomata (I can't translate the ones that they issued in Greek or Arabic). Most commonly they are described as 'rex Sicilie' (king of Sicily) as well as some variant of 'ducatus Apulie at Calabrie' (duke of Apulia and Calabria). So you can see that the Hautevilles defined not only their kingship but also their ducal authority by geographical locations rather than the people therein (Enzensberger (ed.), Guillelmi I Regis Diplomata and Bruhl (ed.), Rogerii II Regis Diplomata Latina).

As far as I know, no one has looked much at why this is. It could be connected to how much of the Hautevilles' administration was derived from structures that were already in place when they arrived - primarily North African Arabic and Byzantine - and the fact that by the time Sicily started to become a kingdom it was under the rule of people who had probably never been to Normandy, but I don't know enough about North Africa or the Byzantine Empire to comment on how they describe their rulers. I think it's unlikely to come from that though - the format of the Latin diplomata is pretty European and even the first generation of Norman arrivals in southern Italy, fresh from Normandy itself, opted for geographical designations. Robert Guiscard is styled 'dux Apulie et Calabrie et ... futurus Sicilie' (duke of Apulia and Calabia, and future duke of Sicily). My guess at an explanation would be the diversity of the populace. With large Arabic and Greek populations, plus Lombards and Normans and probably some others too, it would be very unwieldy to declare rulership of each category of citizen. Unlike somewhere like England or France, southern Italy and particularly Sicily was linguistically, culturally and ethnically extraordinarily diverse. "I'm the king of Sicily and whoever lives there" is probably a more efficient way of defining your authority! It's also more accurate. The Hautevilles took and ruled Sicily, regardless of the identity of the people within. (There's some evidence that they actively worked to officially recognise the different cultures on the island but that's a tangential discussion for another time.) This is just my guess though, and there's definitely room for a proper study to shed more light.

So although rulership of a people is more common, there are examples of rulership of a place, though the ones I know of are the result of circumstances that don't usually arise in most of Europe.