When I taught History of the English Language, I had a lecture on the etymology of the "worst" words in English that I would use to illustrate how historical linguists reason about word histories. Just to cover my ass, I always warned my students what was coming and gave them the option to object and have me illustrate the topic with more innocuous words. Strangely enough, no one ever took me up on that offer.
Olympia's remark here on the etymology is more or less right:
The wisdom goes that it derives from old German, where it was spelled with a k and simply meant female genitalia (kunton, I believe)
This is a not-too-badly mangled version of the etymology you will find in the OED:
ME cunte, count(e), corresponding to ON kunta (Norw., Sw. dial kunta, Da. dial. kunte), OFris., MLG, MDu kunte—Gmc. *kunton wk. fem.; ulterior relations uncertain.]
Unpacking this entry, it tells us that there are related forms attested in a variety of early Germanic languages and some modern ones (although for some of the modern languages, only in certain dialects). That evidence suggests that all of these forms go back to a common form in proto-Germanic, the presumed ancestor of all these languages: *kunton. Connection to any earlier forms, for example an Indo-European root, is uncertain.
Before I move on to my main point, one small quibble with Olympia's wording. Note the asterisk. This indicates that the form is reconstructed by historical linguists. We don't actually have any written records of the word that far back. So it's misleading to say that it was "spelled" with a k, since it wasn't actually written down.
On the other hand, one of the comments proposes an alternative etymology (the writer's native language is not English, so we'll forgive the mangled grammar and spelling):
I believe the the word " Cunt " has its ethimology in the latin word " Cunnus" which designate the vagina...please mind "cunnilingus"
The writer didn't just make up this proposal—in fact when I mentioned this etymology to my wife, she immediately said that she'd heard the same thing.
The connection seems obvious, but notice that the OED declines to make it. Why?
To understand that, you need to know a bit about the way Latin and English are connected and the methods that historical linguists use to determine connections between words.
It would seem obvious that two words with similar sounds and meanings should be related. And there's a chance that they are, but it's always possible that there is simply a chance resemblance.
Think of it this way. Suppose you have two languages, A and B, that are historically connected. In other words, they both derive from a common ancestor language C. What makes A and B different languages? An accumulation of changes in pronunciation, vocabulary, syntax, etc. When we're comparing word forms, pronunciation changes are particularly important.
Over a short period of time, many pronunciation changes are idiosyncratic (one word here, another there), but over a long period of time we can observe patterns to the changes. In other words, a particular sound will change regularly, across the language.
Figuring out what changes have occurred is a complex (and to my mind fascinating) business—a huge puzzle with thousands of interlocking pieces that people have been working on since the end of the eighteenth century.
When you factor in the various sound changes that occur in each language over time, it's not enough to match up the forms of words in two language, you have to make sure they match after all the sound changes have been applied.
So, for example, we can say that English father is related to Latin pater because there is a regular correspondence between [p] in Latin and [f] in English and the other Germanic languages. For some other examples, compare piscus vs. fish, pes, pedis vs. foot, or pedo vs. fart.
Because of a large number of similar correspondences, English and Latin are taken to be related, both members of the Indo-European family of languages. Languages in this family are presumed to derive from a common ancestor, proto-Indo-European (PIE). And since the various sound changes for the Indo-European languages have been worked out in detail, we can check whether two words that look like they might be related actually are.
Sometimes, surface forms can be misleading. For example, the Latin and Greek words for "god" look related: deus and θεος (theos). But Greek [θ] generally corresponds to Latin [f], and in fact these words go back to different Indo-European roots. The root that gives the Greek word (PIE *dhes) also gives Latin festum (feast).
In the case of Latin cunnus, usually translated as "vulva" or "pudendum," we have another example of a misleading correspondence. The sound [k] in Latin corresponds to [h] in the Germanic languages. For example, cor, cordis = heart, cornu = horn; centum = hundred.
So we would expect any English cognates that derive from the same I-E root as cunnus to start with [h]. The American Heritage Dictionary's appendix of Indo-European roots gives the I-E root for cunnus as (s)keu-, which has a meaning of "cover" or "conceal". From this same root, we get English words like hide, hose (as in a covering for the leg), and horde.
Looking at it the other way around, [k] in Germanic languages corresponds to [g] in Latin (and Indo-European), so we would expect any I-E root for cunt to start with [g].
In short, there's no way that cunnus and cunt are cognates that derive from the same Indo-European root.
There is another another possibility, at least theoretically. The ancestral form of cunt could be a borrowing from some I-E language that didn't undergo the [k] --> [h] change. On this theory, cunt would have been borrowed into the language after the sound change occurred. If this happened, we would have a parallel to borrowed forms like cardiac and coronet. Since these words are relatively late arrivals to English, they don't show the effects of the old sound change.
The problem with the borrowing hypothesis, though, is when it would have occurred. Since we have many related forms in the Germanic languages, the word is clearly not a recent borrowing. It would have to pre-date the Anglo-Saxon invasion of England.
Now it is true that there is an early stratum of borrowing from Latin into Germanic. These are words that the Germanic tribes borrowed as a result of their contact with the Roman Empire. For example, words like camp, street, pipe, and cheese all come from this period. However, it seems difficult to believe that cunt was borrowed. First, virtually all of these borrowings are for items of technology, warfare, merchandise, etc. The sorts of things that Germanic peoples would have encountered in dealing with the Romans. Obviously, cunts would have been familiar to the Germanic tribes with or without Roman contact, and it's impossible to believe that they didn't have some preexisting term. Further, even if the word somehow was borrowed, the [t] is unexplained.
If you're expecting me at this point to offer an alternative root for cunt, don't hold your breath. Many people have made proposals, but all of them have problems. The simple fact is that we don't know where the word came from, but we do know enough to reject the superficially plausible connections.
[Update #2: Since I wrote the article above, a number of articles have appeared on the web that purport to discuss the etymology of cunt. Most of them can be described with other four-letter words. Here's a rule of thumb for you: any discussion of etymology that talks about the mystical power of terms for women, or that suggests connections with ancient Sumerian or Egyptian without even a shred of evidence to show how those languages could possibly have influenced English words should be dismissed out of hand. For another piece by someone who actually knows what he's talking about in etymological terms, see this post by Anatoly Liberman, a professor who specializes in Germanic linguistics. His suggestion that it's the n rather than the t that's intrusive is, I think, a good one.]