A lot of Scandinavian lects are said to have common vs neuter gender as opposed to masculine vs feminine, since the common gender came about from a merger of the masculine and feminine; likewise, early proto-Indo-European is said to have had animate vs inanimate genders, and only later split the animate gender into masculine vs feminine. So what we call the grammatical genders — or even whether we call them genders at all, as opposed to noun class — is really a pretty arbitrary thing. This being said, though, it's a mistake to think that grammatical gender must reflect some trait of the referent in any case, and it's also a mistake to think that grammatical gender has absolutely nothing to do with social gender: the truth is somewhere in the middle. So you can't blame Welsh having masculine and feminine genders on Anglo-Saxon sexual hierarchies, because all evidence points to the Celtic languages having had masculine and feminine genders the whole time — proto-Celtic also had a neuter gender.

As far as I understand through half-remembering David J Peterson's book on how to conlang good, grammatical gender/class is believed to first come about through grammaticalization of some sort of commonly-used distinguishing word (think analog vs digital clock e.g.). So basically the distinguishing word gets progressively more reduced as it becomes progressively more overused, until it just sort of fuses into the word it's modifying and is reinterpreted as a grammatical affix of some sort. Then sometimes different distinguishing words are reduced or changed so much that they merge into each other as they grammaticalize; or sometimes words end up being caught in one category or another just because they happen to start or end with a certain associated sound, even if it's just a coincidence; or sometimes words just change genders for any number of other arbitrary reasons.

A system of masculine vs feminine gender specifically as far as I understand probably first started in like overused (socially) gendered baby name components and just sort of spiraled out from there. There's also something to be said about like the animacy hierarchy and obviation or whatever, when it comes to the evolution of the neuter gender, but this isn't really my field of expertise anyways. There's even languages like Italian and Romanian where some nouns behave as one gender in the singular and a different gender in the plural. It's a fuck.

Edit: Also, I want to say that I'm a bit bothered by the other comments here since they contain what I identify as mistakes, but I can't exactly say "pop linguistics and its consequences have been a" from my own armchair.

Grammatical gender can also refer to arbitrary noun classes like animate is one grammatical gender vs. inanimate is another. This is pure speculation but it makes me wonder if the name of "grammatical gender" is based solely on the extant noun classes in Romance languages.

As an aside, English historically was a language with three noun classes (masc/fem/neuter), but this has fallen out of use as the language almost completely (some exceptions might be pronouns and metaphorically gendered "she" for ships) lost its noun classes a long time ago, and now, even many of the few remnants of gendered terms that actually have to do with people's gender (e.g. waiter/waitress => server) are falling out as well.

Edit: Altered last sentence in response to @huf@hexbear.net to properly distinguish two separate phenomena

the original meaning of "gender" (in latin) was "kind" (but also "kin" (a cognate, actually), so there was always a shade of meaning relating to reproduction there).

by the time romans started writing about their grammar, latin had lost its third noun class (i think very originally it also had m/f/n, like germanic languages). so i think already with the romans the concepts of noun class and social gender and sex got confused with each other a bit. at any rate, the romans found latin to have two noun classes, and words like mother and girl belonged to class A, while father and boy belonged to class B, so they ran with that, and called the two classes m and f. and it stuck.

and so in european languages, whose grammars were all written down by people familiar with latin grammar, the conflation was carried forward (and also because european languages often have a noun class system that maps to m/f somewhat).

so it's eurocentrism, in a way, but even within europe, it takes a lot of handwaving to sustain this idea, because apart from words for people and animals, pretending that social gender and grammatical gender are the same concept is difficult.

but yes, grammatical gender is just an arbitrary grouping of nouns into classes. which is why i like the term "noun class" better.

anyway, i think a bit too much is made of grammatical gender, in the sense that it's just as possible to be breathtakingly sexist in a language with no grammatical gender, so it's clearly not a very important cog in the great wheel of oppression.

Hittite's noun classes were for animate and inanimate. This might be what Proto-Indo-European (or before) originally used.

Both Greek and Sanskrit grammarians discuss grammatical gender using "gender" terminology. The author of the "earliest surviving medieval treatise on Greek syntax" was probably synthesizing earlier scholars rather than introducing new terms when he wrote in the early 800s CE. Greek actually has five genders - masculine, feminine, neuter, common, and epicene. Common is for nouns that are "capable of being either masculine or feminine," and epicene is for "a word with a fixed gender used for both masculine and feminine beings."

The Sanskrit word for gender, "linga," appears in Pāṇini's grammar, which may have been written in the 4th century BCE.

Sources:

Ancient Greek Scholarship, by Eleanor Dickey, p. 127, 167-68

Panini