One of the earliest makers of compasses in England was a man by the name of Tate, who developed a hand-held version made partly of metal. For several decades, the Tate's compass became something of a standard. That is, until certain characteristics of the mined iron Tate was using created magnetic effects, disrupting the accuracy of the instrument. Tate and his compass disappeared from history - an episode with left us with the maxim, "He who has a Tate's is lost."
The compass in Civ IV is a severe anachronism; it appears at about the same rank as technologies invented prior to the founding of the Roman Empire, and yet the use of magnetic attraction to determine direction was not in widespread use until the 12th century A.D. Civ IV is probably basing its compass on the rather dubious assertion that Olmecs used magnetism in this fashion prior to 1000 BCE ... even if the Olmecs did understand magnetism, we have no way of telling how they might have used such knowledge.
The principal valuable use for the compass was in the directing of ships, who prior to the compass were forced more or less to travel within sight of land at all times. Points of headland were carefully mapped as an aid for transportation, and memorized by pilots. The tactic worked well for the comparatively gentle waters of the Mediterranean, the Red, the Persian Gulf and for certain coastlines from East Africa to the Far East. It was not useful for the Atlantic coast, as the driving wind was towards the land and journeys along the French coast, smashing ships that picked their way along the coast. The blind journey across the turbulent Bay of Biscay, away from land, was hardly safer.
By making such waterways safe and more easily traversed, medieval sea travel boomed with the 13th and 14th centuries. Moreover, where seasonal periods would create storms or heavy fogs, shiptravel by the stars or by the coast was impossible for months of the year. The compass reduced those poor periods - increasing the number of trips a shipmaster might take in a year by as much as 20 or 30 per cent.
Which begs the question - why isn't a compass a common tool to be found in D&D?
Well, to begin with, most compasses prior to 1500 were fairly cumbersome pieces of equipment, eight or ten inches in diameter, involving either a magnetized needle of some kind floating in a basin of water, or a carefully balanced card, demanding a steady surface upon which to rest. Thus, if the setting corresponds with the period of Robin Hood - as many worlds do - a hand compass is reasonably non-existent.
But there's also to the argument to be made that parties having a compass (perhaps developed from supernatural knowledge) would be far less likely to get lost. From what I understand, 'getting lost' is a central feature in common campaigns. It seems to be an important hook in creating scenarios for combat, trials and so on - a compass would ruin all that.
It seems that letting players have the means to strike out directly across a wilderness just lacks that certain romance of staggering hopelessly in the bush, until the moment comes when the party sees a castle, and are 'saved.' A moment that gets played so often in fantasy fiction, one might confuse it with horror films where a couple's car breaks down and the find a convenient house at the end of a nearby lane.
My world takes place in the 17th century, so naturally compasses are common and available ... as a magnifying glasses, reading glasses, telescopes, sextants and a variety of other technological devices. I haven't noticed that these things damage the campaign, but then I'm strange.
I wonder, however, how often DMs give thought to what ordinary, non-magical devices might bring about a change how they play, and how they 'set up' players.