Origin of the concept
The idea of potestas originally referred to the power, through coercion, of a Roman magistrate to promulgate edicts, give action to litigants, etc. This power, in Roman political and legal theory, is considered analogous in kind though lesser in degree to military power. The most important magistrates (such as consuls and praetors) are said to have imperium, which is the ultimate form of potestas, and refers indeed to military power.
Potestas strongly contrasts with the power of the Roman Senate and the prudents, a common way to refer to Roman jurists. While the magistrates had potestas, they had auctoritas. It's said that auctoritas is a manifestation of socially recognized knowledge, while potestas is a manifestation of socially recognized power. In Roman political theory, both were necessary to guide the "res publica" and they had to inform each other.
Evolution of the concept in the Middle Ages
After the fall of the Western Roman Empire, most institutions of Roman public law fell into disuse, but much of Roman political theory remained. During the early Middle Ages the Christian world was ruled in theory by the Pope and the Holy Roman Emperor. The former had the spiritual power, which was identified with auctoritas, while the latter had temporal power, identified with potestas. At first, the Pope crowned the Emperor and the Emperor appointed the Pope, so they were in a situation of balance, but after the Investiture Controversy the Pope was instead chosen by the College of Cardinals.
As the effective power of the Holy Roman Empire declined, kingdoms asserted their own independence. One way to do this was to claim that the king had, in his kingdom, the same power as the emperor in the empire, and so the king assumed the attributes of potestas.