Fully independent happened very rarely - at least in theory, they were vassal to someone, and even if they fought that off, the theoretical liege lord could at any time with the approval of the papacy, the emperor and other lords come stomping to bring you in line.

Many of these states would be within the Holy Roman Empire and de jure under the emperor.

Calling yourself a King was a dangerous game. It told everyone around you that you wanted to be de jure vassal of none. To accept that you are temporarily not under their thumb was acceptable to many. To shove it in their face and claim to be their equal? Them's fighting words.

Kingdoms existed either through a long tradition (Sweden, Scotland, France, Bohemia, England, Denmark, Norway, Castile) or were created through violence and papal or imperial support (Portugal, Hungary).

Many were de facto independent, few were de jure independent.

The title of king is a European concept and came from the Germanic tribal (word: Koenig) system in the wake of the so-called Barbarian Invasions at the end of the Roman period.

With the ascendancy of Charlemagne, the title of King became intertwined with Papal power. The Pope conferred divinity to the kings; their position as ruler was now part of the conceptualization of Christendom. So the various rulers around Europe who had the title of King were essentially ratified by the Pope after this point. This includes France, Germany, and England.

Spain is the most interesting example. Charlemagne invaded Iberia in the late 700's, conquering a borderland called the "Spanish March". Within that area he conferred several "Kingdoms" and "Counties," appointing Kings and Counts, respectively.

Fast forward a few centuries. The various titles in Spain more or less stayed static, with the exception of the Kingdom of Asturias, which fell apart and was re-shuffled into the kingdoms of Castile, Leon, and Navarre.

Aragon is a more interesting example: in the mid 1100's, the Kingdom of Aragon married into the house of Barcelona, adding the "County of Barcelona" to the King of Aragon's lands. He didn't incorporate Barcelona/Catalonia into the Kingdom of Aragon, because the Count of Barcelona was a more powerful figure AND because the historical significance of both positions, King and Count, held a lot of political and social sway.. Thus he remained "King of Aragon, Count of Barcelona."

Later, in the late 1200's, the Pope convinced James II of Aragon to renounce his claim to the Kingdom of Sicily (a norman kingdom founded in the 1000's) by giving him "The Kingdom of Sardinia and Corsica." This new kingdom was essentially created by the Pope at that time. It wasn't even ruled by Aragon, either--James had to to and try to Conquer it. But not ruling it "de facto" didn't stop him from claiming it "de jure".

TL;DR: Kingship was a title with heavy historical significance; in order to be a legit king, you had to have both political right to rule as well as the blessing of the church.

EDIT: As per peteroh9's correction, it was Pepin III, not Charlemagne, who became King of the Franks with the Pope's help.

In the Holy Roman Empire at least, there was only allowed one king, the King of Bohemia. Eventually the Habsburgs were allowed the tittle of Archdale, but no one was allowed to claim the tittle of King under the system. This is the reason why the King of Prussia was actually the King in Prussia and only a Duke in the Empire (the claiming of the title was a political move but eventually the in was dropped and they were just called the king of Prussia.)

source: The Iron Kingdom

As a sort of follow on to this question, what role did the pope (and by extension papacy) play in deciding who got to be a Kingdom and who was a Duchy, Principality or Marquisette (is that correct?)?