E: Circumlocutions
"Circumlocution" derives from Latin roots meaning "around" and "talk." "Euphemism" is from the Greek "euphemia," meaning "use of good words." Apparently we spend so much time trying to say unpleasant or socially unacceptable things pleasantly that we need two words to talk about the process.
Everyone is familiar with certain euphemisms used to swear in polite company: "heck," for instance, and "darn," both of which have a certain old-fashioned flavor in today's more explicit society. Other euphemisms have become so common most people don't even think of them as euphemisms: while "little girls' room" is too cutesy and saccharine for most, lots of people ask for directions to the "bathroom" or "restroom" or "washroom"/"lavatory" without considering that their actual goal is not to bathe, to rest, or to wash. (Mykle Hansen used to say "Can I use your restroom? I want to take a rest.") You could say that all of those are euphemisms for "toilet"—but that too was once a euphemism.
Euphemisms gradually become closer in meaning and connotation to what they euphemize, until you need a new layer of euphemisms to refer to them. "Toilet" (derived from a French word meaning a shaving cloth) once referred to a dressing table; through a series of steps it began to refer to a washing-up room, and then eventually to its modern meaning. Nowadays it's no longer a polite word (at least not in the US; in the UK it's used on signs in restaurants), but it's still slightly more acceptable than certain other terms.
Similarly, "urination" could be considered a slight euphemism. It's less offensive in polite company than, say, "piss," and may be the only non-cutesy term one can use semi-politely, but it's still a way to avoid saying a really blunt term (like "piss"). I'd say "tissue paper" for "toilet paper" is a euphemism, but I'm not sure whether "toilet paper" is or not—I guess it would depend on whether the term came into use before or after "toilet" stopped being an effective euphemism.
At Mt. Vernon, you can view the "necessaries," the 18th-century euphemism for what we euphemistically call "outhouses." "Chamberpot" and "thunderpot" (a term I've been told is common slang for "toilet" or maybe for "chamberpot" in some places, but have never heard used in actual conversation) are also euphemistic.
Many mild oaths (including "heck" and "darn") began as nonsense words slightly altered from the original word being avoided. "Gosh" is an alteration of "God"; "gee" and "jiminy cricket" derive from "Jesus" and "Jesus Christ." ("Jehosophat," however, isn't an alteration of "Jehovah"—it's from the name of an ancient king.)
I've heard a couple of less old-fashioned alterations along these lines: "sugar" (usually pronounced "shhhhhh...ugar," as the speaker cleans up ta's language mid-word) and "God ... bless it" when it's quite clear the speaker wants anything but a blessing.
And of course avoiding taking God's name in vain is a time-honored practice. Some of my Jewish friends write "G-d" or "Gd" in order to avoid writing the word "God." Going back a ways, people at one time altered words to avoid explicitly swearing by body parts of God: "'sblood" refers to "God's blood," and "zounds" (which modern Americans are like as not to prounounce to rhyme with "bounds") originally referred to "God's wounds." (I'm told there's no truth to the idea that the British all-purpose off-color intensifier "bloody" derives from "by our Lady," referring to the Virgin Mary.) "Odds bodkins" refers to God's body ("bodikin"). Lorrie Kim points out that in Gone With the Wind someone swears by "God's Nightshirt."
Finally, the military is a great place to find euphemisms. There are far too many military euphemisms to list here, but it's worth noting that the Department of Defense was formerly known as the Department of War...
Thanks to Mark-Jason Dominus for suggesting some of the ideas used in this column.