Yes, it did really happen, but it varied a lot (as you'd expect) based on time and place. This answer will focus primarily on continental Europe (England is different and weird, so hopefully someone with more knowledge of the English nobility than me can come along and answer about that) and roughly for the Central Middle Ages, although the principles remained, for the most part, the same throughout the period.

First of all, two points of clarity.

• Although in fiction, kings often created great nobles out of nothing (our peasant boy hero is made Duke of Wonderland by the grateful king after killing the dragon), in reality this never happened. If the king gave you a title, it was because you were already very powerful/rich/influential etc. before you were given it.

• Titles and land-holding are not the same thing. The Count of Anjou or the Duke of Aquitaine did not own all of their respective territories - although they certainly would have held a lot of land there. Similarly, many nobles would also own land outside of their territories.

So, on to the meat of the question: where did this land and the titles come from?

The titles usually came from the King's imagination. There was no 'pool' of available or occupied titles and the King could, in theory, create as many as he wanted. In practice, during periods of stability this rarely happened, and traditional divisions of authority (counties, duchies etc.) were fairly stable. In periods of weakened royal authority, civil wars or general instability, things were a lot more fluid and offices could elapse, new offices could be created and people could even 'promote' themselves without (apparent) royal sanction. The late ninth century is a good example of this, as people like Richard the Justicier, count of Autun or William count of Auvergne transformed themselves into the dukes of Burgundy and Aquitaine, respectively (see also the transformation of the Counts of Rouen to the Dukes of Normandy in the mid-tenth century). Titles could even be granted as simply a way of confirming the de facto rule of an area by a wealthy or powerful individual, as was the case with Landric of Nevers in the 990s: a previously powerful individual who everybody suddenly starts recognising as the Count of Nevers.

The land, in continental Europe at least, was in theory separate from the titles. Kings could and did grant land to people all the time, without giving them any special office or rank. This land came from the king's own personal estates, known in the early and central middle ages as the fisc (from which the modern term 'fiscal' derives). The so-called 'politics of land' was hugely important in the early middle ages, as kings tried to overcome the inherent paradox of rewarding followers with lands while maintaining enough lands to ensure that they would have followers in the future. They maintained the fisc in several ways, including confiscating the lands of traitors and rebels and only granting lands to followers temporarily (usually for the lifetime follower; known as a benefice or a precarial grant). During the Carolingian period, offices such as that of count included control over the fiscal lands of that county, but Carolingian countships were not, in theory, inheritable and counts could be shuffled between counties on the whim of the king. Eventually, the nobility began to demand the right to pass their counties on to their sons, and much fiscal land was eventually lost and incorporated into the personal lands of the count. In the central and late middle ages, grants of land from the king were much rarer and often highly conditional. The most conspicuous alienations from the royal domain were the creation of appanages - lordships for brothers or younger sons of the king, so that the land was kept 'in the family', as such. This didn't always work out well for the royal family - the powerful Burgundian state of the later middle ages started out as a royal appanage, but later became a major headache for the French kings during the Hundred Years War.

TL;DR - Most of the lands came from the king's own lands, the titles were traditional, for the most part.