The most common method of becoming King was to inherit it. If you were the eldest son, you would become King upon your father's death. It took a while for this to be formalised in a number of countries (e.g. William Rufus was not the eldest son of William the Conqueror), but it did make things easier. There was less likelihood of trouble if everyone knew who was next, even if he was an incompetent twerp.
You may be familiar with the Monty Python quote You don't vote for Kings. It's not quite true. It is true that there was never a Presidential style election for a King. That would mean peasants got to vote, and despite the hard work of the levellers, the vast majority of the nobility would never have that. Usually it was a group of interested parties involved, as in the witan. For "interested", read "self-interested land holders who could raise a large enough fighting force to cause trouble if they didn't get their way". As well as the Anglo-Saxon Kings of England, Hugh Capet was elected as King of France.
A King can make a King
We know next to nothing about Hugh Capet, which is a shame because he seems to be a very clever guy. He started a dynasty that lasted centuries without anybody noticing. Nobody thought that there would be a Capetian line of Kings except Hugh, who raised his son to the throne before his death. The two ruled in tandom. Hugh died, his son ruled alone. That is until he raised his own son as co-King. Several generations later nobody questioned that the French crown was hereditary.
Notes about historical Kingship
Although you couldn't generally become King by election, the only way to become Holy Roman Emperor - who supposedly outranked any King in Christendom - was by election by the Imperial Electors. A copy of the Golden Bull of 1356, that defines and regulates the election, is here ...
Another important medieval idea is what a King is ; a King is a Prince who is Sovereign in his own domain, who has either personally or by his predecessor, been invested in the title of King by the Pope.
To be Sovereign means that a State does not have to answer to another worldly power for its acts ; the city of Florence is sovereign, while the city of London is dependent on the King of England and thereby not. If a city or a state makes war without the command of another, then it is almost certainly sovereign.
Note that some Princes who are not titled Kings, such as the Counts of Savoy, are sovereign, as in no other Prince can lawfully command them ; but although they are Emperors in their own domain, they do not have the title of King.
The Lord of Milan, Gian Galeazzo Viscounti bought (as in, for cash) the title of Duke of Milan from Emperor Wenceslas in 1395; he attempted to be invested with the title of King, but this was not granted by the Pope.
Another example of an elective Kingship is 16th Century Poland ; after the death of Zygmunt Augustus, last of the Jagellonian dynasty, in 1569 they elected the French prince Henri of Anjou as King of Poland. This worked badly, especially when the noted party animal and hedonist Henri realised the limited entertainment opportunities available in Poland. He quit the job soon afterwards, and returned to France to be crowned King Henri III of France.
Becoming King in the SCA
The usual way to become king in the SCA is to win a crown tournament. A less common way to become king is to be the consort of a fighter who wins crown tournament. As a method for choosing a king, it has a number of advantages. The main one is that in order to be good enough to win a crown tournament, it is likely that the victor will have been involved in the SCA for a respectable amount of time.
There are a few drawbacks with this, not the least being that certain SCA demographics are over-represented. This is probably not as much of a problem as some may think, as the first three reigns of the Kingdom of Lochac saw three Laurels take the throne (two Queens and a King).
Argument for the SCA's Method of Determining a King
Surprisingly, one of the arguments that is sometimes promulgated for the crown tournament model of selecting Kings and Queens is that becoming King by right of arms is period. Certainly, it is true that many Kings were crowned after having conquered a Kingdom, but none became King by winning a tourney.