A lot of the answer to this question comes from where you draw the boundary between a 'tribe' and a 'nation state', but when I studied European History 900-1215, it did cover a lot of early state formation, particularly in France and Germany. I'm more familiar with France, so I will focus my answer on that.

In 900, 'France' as a political unit was extremely fragmented. Regional rulers - usually Dukes - controlled most of the country and maintained their own armies. Loyalty pledged to the crown was largely for pragmatic reasons as the support of the king provided legitimacy against competing claims and could be used as an arbitrator in ducal disputes. This didn't stop Dukes from seeking to increase their wealth and authority. The most notable example of this would be the Dukes of Normandy, who ultimately conquered England and thus became, while nominally subservient to the French King, rulers of their own kingdom.

The French monarchy (the Capetians) did control the Ile de France (the bit around Paris) which was the richest single region, but otherwise they had extremely limited political authority. After the Normans took England, they ceased to even be the richest family in France. So as late as the 11th century, you can see that the French monarchy has extremely limited power. There was no real central government and, beyond the Ile de France, the real ruler was the local Duke. Honestly, the more I studied it, the more I was curious why these local leaders even bothered to stay aligned to France! My readings mostly indicated that allegiance to the throne helped to legitimise their positions as well as providing potential political support in disputes with other leading families.

The Capetian dynasty successfully navigated this landscape of competing loyalties by the expedient measure of living a long time. From Hugh Capet's death in 996 to the death of Phillip II Augustus in 1223, there were only six Capetian monarchs, each with an average reign of 38 years. In contrast, England had (by my count) seventeen separate monarchs. The shortest rule was 29 years (Henry I 1031 - 1060 and Louis VI 1108 - 1137). As a result, they avoided many of the succession crises which weakened competing dynasties - for over 200 years, the Capetians avoided the problem of putting a child on the throne. Child monarchs require protectors, which in turn encourages competition among the major families of the kingdom, many of whom will then attempt to supplant the monarch. Instead, Capetian kings in this period lived a long time and gained considerable experience in statecraft.

This advantage manifested itself through (roughly) a period of consolidation followed by a period of reform. Louis VI and Louis VII can be seen as the major consolidators, using careful strategic marriages to build up possessions around the Ile de France, as well as developing the economy of their land by establishing market towns. While these steps certainly contributed to wars with the Angevin English monarchs, they enriched the French treasury.

Another major step was the role of the Church in legitimising the Capetians. Louis VI and Louis VII both had a close relationship with Abbet Suger of the Abbey of Saint-Denis. Suger helped both Kings build a close religious affiliation with the Abbey, providing them with religious authority to claim obedience. On a more pragmatic level, the Church provided administrators. As clergy could not have legitimate children, they made excellent administrators as (at least in theory) their titles and roles reverted to the crown on their death, as opposed to the laity who would expect to bequeath titles to their children. In this way, the French monarchy built both legitimacy and a formidable administrative apparatus.

Phillip II Augustus (1180-1223) was perhaps the key to making France a 'nation' by any definition. A strong strategist, he led France to military success over their enemies, breaking up the Angevin Empire and cementing his position as paramount leader of France. By marriage, he acquired the rich regions of Champagne which, combined with earlier Capetian marriages which built control over Picardy, enabled direct royal control over a far greater region of France. The wealth of these regions enabled the French monarchy to cement their control, building many of the institutions which became what we now view as the French state.

It is tempting to view this as a relatively coherent storyline of consolidation and expansion, but in reality it was a lot more uncertain. At key moments - for example, after Eleanor of Aquitaine married Henry II of England, or when Philip I was excommunicated - it would have been possible for the Capetians to fail. Their success was ultimately based on sound economic management, the development of a strong administrative class, good military management and a successful project of religiously-focused legitimisation. While their longevity may feel like a slightly simplistic explanation, it was undoubtedly a major asset to this process.

Of course, this doesn't completely answer your question. In 900, the idea of 'France' already existed to some extent in the minds of leading families in France. Similarly, by 1223, France was still a long way from a modern nation state. The true process by which modern nation states emerged is incredibly long and goes back about as far as you care to go, but this period is at least an interesting insight into how monarchs consolidated power and built the foundations of their modern successors.

I'm away from the computer which contains my sources on this, but I will try to remember to add some references later!