Maybe /r/linguistics would know.

Most of our swear words come from old norse or anglo-saxon. Cunte is saxon for c#nt and ears (ee-arse) was saxon for a#s for example. They are very similar to todays. My guess was that the vulgarity of the words came from norman invaders who considered these saxon words of their serfs to be vulgar. I also can't speak for non-germanic swear words either.

Typically speaking, curse words (we'll come back to that in a bit) are very culturally context sensitive.

Take the Quebecois in Canada, for example. Most of their curse words are centred around the church (tabarnac) or Catholicism in some way. In this vein, some of that is still held in English (Damn, from Damnation, again more on this in a bit).

Just for the sake of expediency, I'm going to move to the Latin, Di te perdant, meaning May the Gods damn you. The idea of damning or invoking God(s) or other spirits to curse one's problems or enemies is the root of curse/swear words. Indeed, the very idea of a "curse" envisions that the words spoken by another have the power to move forces which can effect change. These are seemingly ubiquitous, as Muslim households have ways to hope terrible things happen to someone or insult them without directly stating you hope they die or go to Hell, Japanese households have an impressively large variety of ways to insult others, and Aboriginal cultures also have a series of both racist and general means of insulting or cursing one another (Eskimo is a Cree label for the Inuit, a none too polite one at that).

Now, as you've asked more generally about the bodily excrement and sexual exclamations, I'll touch on them a bit too. Catullus is a fun way to show that sex, sex acts, and sexuality in general have always been a location of and for mocking/expression of anger. In various poems, Catullus uses "sexually submissive" as a derisive way to mock either an enemy or a buddy, dismisses the use of the "shitty papers" of Volusus, etc.

What I'm getting at with this is that human excrement has rarely been viewed positively or "romantically" and thus it is only natural that something awful, repugnant, or otherwise unpleasant would be connected to "shit." As to the sex and sexuality section, while different cultures view such things very differently (the submissive male in homosexual intercourse was viewed much more negatively by the Romans than the dominant male, and sex itself while nominally sacred was never portrayed as a shameful or wholly private affair in pre-Christian Rome). Indeed, one need only do a bit of research on Greek or Roman comedic plays to know that sex and sexuality were much less "hidden" than one might presume.

An interesting but impossible study would be to examine whether Cunctator actually transitioned from an insult to a compliment during and after Fabius Maximus's dictatorship. By this I'm trying to more directly address your question as to "how" such words gain their negative connotation. I guess the short answer is that a few things are usually universally associated with negatives (excrement, death, Hell, weakness, etc.) and others are often the site of competition, pride, or intrigue (sex, procreation, property, power), while still others are so contextually specific that they don't make any sense unless you understand the culture.

The fun thing is that by "learning" to associate certain words as "bad" words or phrases, when a person stubs their toe and lets loose with a "shit" or a "fuck!" there are actual physiological responses in the body. By letting loose in this way, a person actually releases a small amount of stress, so a learned behaviour and an associated act (though culturally specific) have species-wide effects.