Non-natural grammatical genders in Indo-European languages:
What is their origin (assuming that there is a single origin, if there are many origins)? Or what are the origins?
At a glance, there doesn't seem to be a point in differentiating the inflection for adjectives and verbs related to the moon and the sun, for example.
If you're talking about why there is such thing as a neuter gender at all, I mentioned in my answer to this question that many believe the masculine/feminine/neuter paradigm of so many IE languages is derived from PIE first distinguishing between animate/inanimate nouns, then the animate noun category began to distinguish between masculine/feminine (link).
If you're talking about why certain nouns are part of specific genders, I too would second the recommendation of Lakoff's Women, Fire and Dangerous Things (link). It's a really interesting exploration of hierarchical cognitive models using some case studies as a guide.
EDIT: Here's is Foundalis's closing to his paper Evolution of Gender in Indo-European Languages.
An alternative hypothesis is that masculine and feminine assignments to inanimate objects existed even in the original Indo-European ancestor. Although such assignments seem nonsensical today, they might have “made sense” in the remote past, at least among the few speakers of the ancestor language, based on animistic conceptions of the world. It could have appeared natural to a particular culture that, for example, a stone is of female sex. However, as the original language evolved, ideas about the stone’s sex changed, too. Since there is no objective way to agree on something like the sex of a stone, the “opinions” among descendant languages evolved differently. What we observe today appears as a purely formal and arbitrary assignment, since the original “reasons” have been lost. One prediction of this hypothesis is that gender evolution in such languages should be traceable through a weak agreement between phylogenetically proximal languages. I believe the present work supports this implication, although further investigation of the hypothesis is clearly needed.
This doesn't answer how it occurred, but offers a why: my two cents is that gender is useful since it can help free up word order, ease reference to antecedent words -- basically make communication more efficient.
Assume more than one origin.
According to the book "Women, fire and dangerous things" (that's a noun-class/gender in an Australian language IIRC) by George Lakoff, it arises due to association. It is not "invented"! In the case of the book title, "women" had natural gender feminine. Since women tends the fire, "fire" received feminine gender. Fire is dangerous, ergo "dangerous things" received feminine gender.
Another route, which might be more likely for Indo-European languages, is sound shifts. The markings for two genders become similar for all/some words and the two genders merge. Or, some words of gender X start to sound like words of gender Y due to sound shifts, and change genders so that the system of markings will still make sense. Instead of sorting into genders according to what the words mean you can now just sort them by what they sound like. Note that different dialects may consider the same word to be of different genders...
See the book "Gender" by Greville G. Corbett if you really want to dive into the subject.
You could ask the same of any kind of agreement: plurality, case, etc. multiple language elements in an utterance that don't add any extra meaning. Grammatical gender is particularly outstanding because it seems so arbitrary.
One explanation is that redundancy provides some error correction over the noisy speaking-hearing connection.
In addition to what kaleissin and Mitch have already mentioned, for Indo-European in particular there was at some point just an animate/inanimate ("common/neuter") distinction which aligned pretty well with actual animacy; English "water" and Latin aqua are descended from an inanimate and an animate word, respectively.
There was for neuter nouns a collective marker **-a*, originally a laryngeal **-h2*, that seems to have developed into the feminine gender.
How did genders and cases develop in IE?
One conjecture is that collective nouns often were used for cows, ewes, does etc.
I have often wondered if gendered nouns might have nothing at all to do with gender, but rather that there developed different classes of nouns in usage, and that only when grammarians first started to parse language (i.e., the Greeks) did some ancient thinker decide that one class of nouns might be considered "masculine," and the second class "feminine) and then when Greek -- and mainly Latin -- grammar was overlain on other languages did the terms "masculine" and "feminine" become common, and a third class of nouns (as in German) would then naturally be "neuter." There must be some other language in which there are four classes or more of noun. Is there any record of the terms masculine and feminine being used for nouns before Aristotle?
Well no one knows for sure and the veiw that second declension nouns evolved out of collective nouns fits the known lexicon better than any hypothesis I know of . This also explains the the mistaken nexus with the female sex since many animals herded as females yet the singular animal was usually or often the male ( lupa/lupus). Even in English "vixen" is an old plural/collective form. There is a similar thing going on with abstract nouns which is manifested in modern Italian as the singular "a" ending that is really an ancient plural form. To demand certainty is to ask too much.
i agree with Richard Nilsen's answer.
i want to answer with my words, adding some details.
i think, gender is side-effect of fusion.
i think, indo european languages were agglutinative, and have developed into being fusional, and, so, the fusional morphemes has started to modify root morpheme, and they had to modify different root endings differently. for example, if there are words "abo" and "aba", a morpheme "i" better should not make them both "abi", but, for example, "abe" and "abi". so, people have acquired an extra noun categorisation , which has no meaning, but only for technical purposes, and they decided to use that categorisation also for meaning. then, they decided to use one type of root ending as masculine, another as feminine, or another way (for example by count) but not all objects in world are divided by this categorisation, so, as side-effect, they have become "non-natural genders".
