The answer to your question obviously depends heavily on location and era. I can gve you an overview of how medieval nobility in Western (Christian) Roman Europe came to be:

Sometime between 192 and 235 CE what was known as the "Pax Romana" came to an end. The concept in itself has its problems, but for the purposes of this overview you can imagine that during this time, which spans from 27 BCE (ascension of emperor Augustus) to (at the latest) 235 CE (beginning of the Crisis of the Third Century) the interior of the Roman Empire was largely at peace and one could travel and trade across its territory with relative ease. This lead to the development of a complex society and an integrated economy with (relatively) large cities all over the empire full of specialized tradesmen supported by equally well organized agriculture and food imports from the empire's most fertile provinces.

The (Western) Roman Empire recovered most of its strength after the Crisis of the Third Century and indeed again in the early 5th century before finally dissolving in the late 5th century. Life in the successor states of the Western Roman Empire wasn't all that different for ordinary people and local administration often just stayed the same, with a curia of politically powerful people (kinda like a regional mini-senate) running things as they had for centuries prior.

Still over generations Western Europe in its entirety changed a lot. Gaul, Britannia and Germania were never very prosperous provinces and profited a lot from food imports and even comparatively rich Hispania was mostly cut off from this due to the sustained rise of piracy in the Mediterranian. After it's conquest by the Moors in the 8th century the path of the Iberian peninsula somewhat departed from the development in the rest of Western Europe, anyway. Italy is a bit of a special case, since it remained connected to the (Eastern) Roman Empire up until the high middle ages to some degree.

Lower Nobility and Gentry

This meant that local self-suffiency became much more important again and in many regions the only reliable source of sustenance. The rural areas there simply couldn't support cities of the same size as the prosperous 1st and 2nd century had. Since the wealth from trade also mostly vanished, demand for luxury goods dwindled too and so people began moving from the cities to the countryside in search for employment.

Roman Agriculture at this point had been somewhat consolidated into large estates and did even more so, as farmers looked for protection from increasing numbers of bandits roaming the countryside. People flocked to these estates and became coloni, half-free denizens of the estates and ancestors of the later serfs, which were bound to the land they lived on. The owners of these estates became the gentry and lower nobility of the early medieval period.

Higher Nobility

The higher nobility evolved in a different way. Roman state structure didn't simply disappear. The "barbarians" who took over Western Europe had (been) thoroughly romanized and didn't want to destroy the roman state, but rather to take it over and enjoy its many benefits. During the turmoil some damage was obviously done to the civil service, but a lot of offices and administrative divisions remained or adapted to the new circumstances. Early medieval successor states were surprisingly centralized in their power structure (though wether any one specific ruler could actually enforce this was another question) and became even more so under Charles Martell, Carloman and finally Charlemagne (the Karlings). Only after the latter's death did power devolve lastingly.

What we think of as titles of the higher nobility used to be offices within or under the royal court. Counties were administrative regions and counts (comes, literally "companion(s) (of the Emperor)") could hold more than 20 counties, if they were influential and capable. These possesions were not hereditary though and try as they might, counts didn't really have the means to force a king to make them so. Counties were regularily taken away from counts and this was not seen as punishment of shameful (though sometimes it was meant to be), but rather as an act of administration.

Dukes (dux, "leader") were military commanders whose office originated in the Roman Empire after the reforms of Constantine the Great and survived the dissolvement of the Western Roman Empire. They were commanders of the troops in one roman province, which used to be much larger than the counties which made up the administrative structure of the early medieval period. The office remained in similar capacity and thus dukes were placed "above" counts (although they were really meant to be somewhat seperate, but that didn't hold) since they commanded troops for an area encompassing several counties.

Emergence of the nobility as an independent power

Earlier in Britain and Germania, somewhat later in Gallia, but generally as more time passed since there was a central roman administration to hold things together in a grand sense, and thus by the latest during the 9th century, the power of the monarchs declined and soon they weren't dealing with subordinates anymore, but with competitors for power. To keep their vassals on their side in their struggle against other vassals, the monarchs had to keep them happy and when there was no more gold to give, this came in the shape of hereditary estates and later on titles and all kinds of rights (e.g. levying their own taxes, dues and customs, minting coins, jurisdiction). From here on a lasting struggle for power emerged between monarchs and high nobility, which would last until the early modern period, when lasting centralization slowly emerged again.

By then the nature of the relationships between monarchs and high nobility had changed again and I'm not qualified to speak about that. My knowledge ends some time before 1,000 CE. By that time the nobility had already solidified itself in Western Europe and was there to stay, a power in its own right often on par with the monarchs they nominally served.

My main source is "The Inheritance of Rome: A History of Europe from 400 to 1000" by Chris Wickham and assorted essays and articles which I can't remember off the top of my head. I'll gladly dig something up if you have further questions, though it may take me a little while :)

EDIT: typos, grammar, wording, sentence fragments.

Hey, I am someone curious about history and hope to do a history major one day. I might not be knowledgeable about Europe in general, but I want to give a detailed response about Turkey. I hope replies about a specific area qualify. Not traditionally Christian European but I think it is interesting. Our nobility never went feudal. Ottomans were always over-centralized. These noble families mostly were influential families of bureaucrat or soldier descent. They had high ranks in military and places in Ottoman council, Divan. Most of viziers were among them too.

In Ottoman Turkey's first eras they were mostly descending from famous and succesful Akinji begh's who were leaders of Akinji's, a kind of special ops. Those were mainly Turkish at origin. Some were remnants of "uç beyi"s, border beghs appointed by Rûm. We can count Samsaoğulları which descended from Sergeant Samsa, a friend of Osman I among those but there are plenty others. Evrenosoğulları descended feom Haji Evrenos Begh, who was either a Serbian or Catalonian mercenary converted to Islam. Mihaloğulları descended from Mihâl Begh, who was a Greek governor and friend of Orhan I who later became Muslim. Malkoçoğulları descended from some soldier called Malkoç. Germiyanoğulları were ruling dynasty of another Anatolian principality which was inherited by Ottomans. This era lasted until Mehmed II, an is known as Founding Era of Ottomans. Ethnic Turks and voluntarily converted foreign nobles were the influential families. Also Palaiologos family, last Byzantine dynasty, was still active and they held duties in Ottoman court. But Komnenos' were not that lucky. They all got executed because Mehmed II claimed to be of Komnenos descent and didn't want any claimants to his throne.

The later area until 1700s saw a strong decline of nobility due to establishment of many state institutes and centralization. Ethnic Turkish akinji families mostly got dismissed by Murad II, because they were competing the Ottoman family or so thought the Sultan. And Janissaries became the strongest faction in military. The main reason Ottomans took janisseries and sultan's wives as slaves from Balkans and Ukraine was that if they would have chosen Turks, influential families may form. Those converted slaves known as devshirme's served their purpose and couldn't form a nobility. In this era viziers were mostly of devshirme origin, and even most significant ones like Sokullu Mehmed Pasha(A Serbian and a perfect statesman) and Ibrahim Pasha of Prag(son-in-law of Suleiman the Magnificent, a Czech) haven't formed a dynasty at all. I can think of only one note-worthy family in this era, Turko-Greek Barba Rossa's, Hizir Hayreddin and Oruç Nasreddin Pashas. They were independent pirates at first, then became Ottoman subjects. Zapólio's, Ottoman vassals at Hungary are also somehow note-worthy.

Starting with 1700s and until the end of Ottoman reign, military families were lost to history and Janissaries also saw a power decline as they corrupted and degenerated, and finally got abolished in 1821 by Mahmud II, a reformist sultan. Albanian and Circassian families serving as bureaucrats at court gained importance. Some of them are still reputated even to this day. I think in this last era of Ottomans, there are three very interesting families being Kavalalı, Köprülüzâde and Giritli families. Kavalalı's reigned over Egypt as an autonomous Ottoman subject for a long time, and they occupied their way to Anatolia in some point. They are one of the most notable figures of Egyptian history. Köprülüzâde's, as son and father, were best viziers Ottomans saw, maybe after Sokullu Mehmed Pasha. Their grandson Mehmet Fuat Köprülü is considered the founder of methodical history in Turkey and he was a mentor to some of other important Turkish historians like Halil İnalcık, Mükremin Halil Yınanç and Feridun Emecen. Giritli's were not that important maybe, their name literally meaned Cretan and they were... Cretan. They migrated to Tunis in the 19th century. Their descendants reaching to numbers like 20.000 still live there, and are mostly pale skinned and light haired people looking different from Tunisians.

Also not an exact nobility but I think it somehow qualifies. A notable portion of Kemalist and Nationalist MP's and politicians in Turkey are descendants of soldiers in Republican Era. The father of Ümit Özdağ, an influential MP and an anti-refugee activist, was a general involved in a coup d'état. Alparslan Türkeş, founder of ultra-nationalist MHP and Gray Wolves was a colonel too. Meral Akşener, founder of conservative liberal IYIP descends from a family which was influential in West Thracian Republic.

So summarizing. Ottomans were a European power for long centuries and their bureaucracy certainly had remnants of that of Byzantines, so they might give us an example about how do nobility form in a centralized European state. You see, there were three most common backgrounds for Ottoman nobles. First where devshirme's, converted slaves from Caucasus and Balkans. This is not common for other parts of Europe I think, as the devshirme system was unique to Ottomans. Second are soldiers and bureaucrats who gained influence, success and wealth. I would guess this kind of people also rose frequent to nobility in other countries of that era. Third are foreign noble families, when their countries got invaded or voluntarily. This also should be common in Europe too, not sure about the latter but when you invade a country, directly appointing new local rulers surely doesn't help integrating process. It was about only one south east European state which is of Asian origin but I hope my answer was helpful.