(I did a number of Purim related words last year - you can see them in the category "Purim". If you can think of any others to discuss, feel free to let me know in the comments or by email.)
The word medina מדינה appears in the book of Ester many times. According to Kutscher (Milim V'Toldotehen 20-21), in the Bible (Ester as well as Melachim, Yechezkel, Daniel, Ezra, Nechemia, Kohelet and Eicha) - medina, both in Hebrew and Aramaic, always (or almost always) means "province" or "district".
However, in Rabbinic Hebrew, Kutscher writes that the word usually means "city".
How did this change come about? In this article, Professor Charles Torrey writes that there is evidence of medina meaning "city" as far back as the 5th century BCE. He describes the difference in meaning as follows:
The regular Aramaic word for 'city' in both Western and Eastern dialects was medina. This was certainly true during the period of Persian rule in Western Asia and thereafter, whatever may have been the case at a still earlier date. There is no clear evidence that the word was ever used in any other meaning outside of the Hebrew territory. The borrowing by the Hebrews seems to have taken place in the way which is illustrated in countless other instances in the history of language, the new word being given a new meaning by the borrowers. Having a fixed term of their own, עיר, for 'city,' as well as the locally used קריה, they adopted the Aramaic מדינה (literally, 'place of government,' 'seat of jurisdiction') giving it the meaning 'province,' 'sphere of jurisdiction' (equally justified etymologically), for which they had no other term; this signification was very possibly suggested by an old native use in the sense 'capital city' of an administrative district, the same use which we find adopted by the Persians and employed in Egypt. Thenceforward the word meant 'province' in Hebrew-Jewish writings, until at some time in the early Christian period its use in this sense was crowded out by the regular and original native Aramaic use.
So according to this theory, the word medina originally meant "jurisdiction" (from din דין - law) in Aramaic, with the sense of "city", was borrowed by Hebrew to mean "province", and then as the Aramaic influence on Hebrew grew, came to mean "city" in Hebrew as well.
This helps us understand the midrash in Ester Rabba 1:1
כל מקום שנאמר שדה - הוא עיר. עיר - מדינה. מדינה - אפרכיהFor those people reading the midrash when it was written, there was a need to explain why the word medina in the book of Ester did not mean city, but rather province.
"Whever you find (in the Bible) the word field (שדה) it implies "city" (עיר), wherever you find city (עיר) it implies a medina ("metropolis" according to the Maurice Simon translation or "capital" according to Jastrow), wherever you find metropolis (מדינה) it implies province (אפרכיה)."
Arabic adopted the word medina as "city" from Aramaic, and Kutscher points out that this is where the Arabian city Medina gets its name. Stahl writes that this name was originally given to the city by the Jewish residents. This Philologos column also discusses the issue:
We thus know that whoever settled in Yathrib and gave it its non-Arabic name of “the Medina” or “the city” were originally Aramaic speakers from elsewhere. At first this was just a local usage employed by these immigrant Medinians for their town, just as New Yorkers, when talking among themselves, call New York “the city,” too. (If you come from Philadelphia, on the other hand, you call New York “New York,” just as other Arabians went on saying “Yathrib.”) This usage must then have spread to the Arabic-speaking population of Yathrib, which attached the Arabic definite article to make it “Al-Medina” (as Arabs call Medina to this day), a form then adopted by the Aramaic speakers when they eventually switched to Arabic themselves. And it is highly likely that these immigrants were Jews from Palestine or Babylonia, both Aramaic-speaking areas in the early centuries C.E., because we also know from Arab historians that, in Muhammad’s time, three large Jewish clans — the Banu-Nadir or “Sons of Nadir,” the Banu-Korayzeh and the Banu-Kainuka — dominated the city. In addition, there were in Medina two large non-Jewish clans, the Aws and the Khazraj, whose origins were in Yemen.
So we've seen medina meaning province and city. What about the modern meaning of "state"? Daniel Elazar writes:
Both Kutscher and Torrey relate to the Greek translation of the word medina in their efforts to understand its meaning at the time. A common translation is "polis" - the Greek word for "city-state". Since the Greeks blurred the boundaries between cities and states, perhaps any translation of the Hebrew/ Aramaic medina would be similarly blurred.
There is no generic term for state in the Bible or the Talmud. The Hebrew term medinah, now used for state, appears in both; in the Bible it refers to an autonomous political jurisdiction (the equivalent of a Land in German or one of the fifty states of the United States), that is, a territory under a common din (law), whose identity is marked by having its own political institutions but not politically sovereign in the modern sense. In the Talmud, the term is used even more vaguely from a political perspective, as in medinat hayam, roughly translated as some distant jurisdiction. Only in modern times did medinah come to be used to describe a "sovereign state."
In any case, modern Hebrew uses both medina and "polis" - we have mediniut מדיניות - for "policy", but politika פוליטיקה for "politics". And while medinai מדינאי and politikai פוליטיקאי - are basically synonyms, medinai - statesman sounds a bit more noble than politikai - politician.