It’s highly arbitrary. Native speakers like me can’t explain it, and several of us have already tried. On behalf of my ancestors, I apologize. I’m going to list a bunch of weird exceptions and corner cases, but before I do, here’s some practical advice: try searching Google or Google Books for both ways of saying it, and see if one is much more common than the other. There’s no simple rule, but that’s the fastest way to get an idea of how people talk.
For example, several of the answers say that of is “never” used with mountains, but there is at least one exception: most translations of Genesis 8:4 say, “the mountains of Ararat.” But some modern ones say, “the Ararat mountains.” (Unlike many grammatical quirks of English Bibles, this isn’t the result of an overly-literal word-for-word translation. There is no preposition before “Ararat” in the original Hebrew.)
Another answer that’s mostly-right says, “It's a matter of whether the classification (River, Bay etc) is felt to be part of the name or not.” However, the official website for Atlantic City says, “It’s a GREAT Day Here in The City of Atlantic City.” I admit, this sounds ridiculous to me, but a quick search shows many examples like “town of Levittown.”
In aristocratic titles, of is nearly always used in English (United Kingdom of Great Britain and Northern Ireland, Kingdom of Thailand, Principality of Monaco). This is consistent with “Ruler of Place” but less so with “Empire/Kingdom/Principality/Duchy/Whatever of Wherever.” Even German aristocratic names with zu or von und zu instead of von are normally either translated “of” or left untranslated.
The one rule that I truly can’t think of any exceptions to is: we only put of before a name that’s a noun, never one that’s an adjective. For example, either “the Sargasso Sea” or “the Sea of Sargasso,” or the “Sea of Japan,” but the names of most other seas and oceans are adjectives: Pacific, Mediterranean, Caspian, Antarctic. These are never preceded by of.
As for how it got that way? My best guess (I am not an expert) is that the English borrowed it from Latin.
Way, way back in prehistory, the Proto-Indo-European language, the ancestor of nearly all the languages of Europe, had suffixes for nouns that marked where or when things happened. (And observe that dates work similarly: we normally say “January fourth” or “January four,” but there is also a more formal construction, “the fourth of January.”) Today, we call that the locative case. Latin originally still used it, but by the time Rome became an empire (either the Roman Empire or the Empire of Rome, take your pick) these very old noun endings merged with others that happened to sound similar. For a lot of feminine singular names, that meant -ai turned into -ae, an ending that would often translate to of. (If an agricola is a farmer, agricolae could mean farmer’s or of the farmer.)
So, in the Bible verse I quoted above, which most English Bibles translate as “the mountains of Ararat,” the Latin version of the Bible that was used in England for centuries does use the -ae ending (“montes Armeniae”). Educated English-speakers often tried to imitate Latin grammar in the past. This matches the formality of the construction in English, its use for locations and dates, and that it only is used with nouns.
Unfortunately, like learning the history of why irregular plural nouns and past-tense verbs are the way they are, that won’t actually help you learn them.