Not really a question for r/askhistorians (rather r/linguistics) but luckily I'm a philologist with a background in general linguistics – I'm also writing an MA thesis on grammatical gender and language contact. I feel that you're asking two things: 1. Where does language come from – how do we give names to things and 2. How do people know what gender nouns are? I'm just going to focus on the second, because the first is almost impossible to answer.

First of all, it's important to understand that what we call grammatical gender is a type of noun class. Noun classes group nouns based on certain characteristics. One of these can be gender, but in some languages, you find noun categorization along different characteristics. These can be things like whether the noun's referent (meaning the thing it refers to in the real world) is alive or not, i.e., animacy. In Dyirbal (a language spoken in Northern Australia) there are noun classes based on things like whether the noun's referent is alive or not, edible or not, dangerous and not, and so on. Nouns whose referent is biologically male or female fall into different categories – hence the title of George Lakoff's book Women, Fire and Other Dangerous Things.

So let's talk about grammatical gender. Nowadays, most linguists who deal with grammatical gender would say we can only speak of grammatical gender when the noun classes are defined along a sex-based divide. It's important to realize that less than half of the world's languages have sex-based grammatical gender; it's kind of a coincidence that some of the largest languages, such as English*, Spanish, French, Russian and Arabic (to name a few) have sex-based noun class systems.

In almost all of these languages, as far as I know, there are different strategies to assign grammatical gender to a noun. Most importantly, whether or not the noun's referent has a biologically male or female counterpart. There are no sex-based gendered languages (that I'm aware of) that assign masculine gender to nouns with a female referent and vice versa. This is what we call semantic gender assignment

At this point there is usually some wise guy who'd say "Ah! But what about German Mädchen! It's das [neuter] Mädchen, not die [feminine] Mädchen!". And they'd be right. This brings me to the second important way of assigning gender to nouns, i..e, what kind of sound(s) the noun ends on. This is what we call morphophonological gender assignment. Basically this means that the ending of a noun (in this case German diminutive -chen) can override our "logical" understanding of its gender. But it gets more complex. There are few German speakers who would say Das Mädchen, es ist schön i..e, "The girl, it is beautiful" (although this is historically more common). More often, they would refer to back to the neuter noun with sie, ("she").

These two strategies are the most important as to deciding gender. A lot of people, both lay linguists as well as language enthusiasts feel that gender assignment is random. This is untrue. For the vast majority of nouns in languages with sex-based grammatical gender, there are patterns that are rather strict. Learning these patterns might be difficult, and sometimes certain nouns have undergone such sound changes that finding these underlying patterns are very difficult.

In the case of Indo-European languages, it is generally thought that the masculine-feminine divide originally came from an animate-inanimate distinction. I've not done a lot of Indo-European linguistics, but if I remember correctly, at some point animate split up into a masculine and feminine distinction, and inanimate turned into neuter. Then, in some Indo-European languages the old inanimate disappeared, and some (like Baltic) only maintained a masculine-feminine distinction.

In short, depending on where our ancient friend might be living, they'd have different strategies of deciding whether or not a noun is masculine, feminine, neuter, or maybe something else.

For further reading, I'd suggest:

​

1. Corbett, Greville G. 1991. Gender. Cambridge: Cambridge University Press.
2. Fodor, István. 1959. “The Origin of Grammatical Gender.” Lingua 8:186–214. doi: 10.1016/0024-3841(59)90020-8.
3. Steinmetz, Donald. 1986. “Two Principles and Some Rules for Gender in German: Inanimate Nouns.” WORD 37(3):189–217. doi: 10/gfzsbj.
4. Poplak, S., and Pousada, A. 1982. “Competing Influences on Gender Assignment: Variable Process, Stable Outcome.” Lingua 57:1–28.

So, grammatical gender. Before even starting, I want to say that unfortunately, most of my examples will be limited to Indo-European languages, because I'm most familiar with them. And even there, I'm only fluent in English and Romance languages, though I can read Latin. But even if the examples aren't drawing from a universal set of languages, the concepts should hopefully illustrate how this works in other language families.

First thing to point out is the word gender means type. In French, for example, the word is genre, the same word use to talk about types of films or music and it's also the same word used to talk about genera in biology. English just borrrowed various copies of the same word, obfuscating the meaning of the word to a degree.

There are a few ways for gender to manifest in a language, one is sometimes referred to as "natural gender", which is when a real world characteristic is used to determine type. Common characteristics are animacy, humanness, and biological sex. English uses this type of gender for pronouns, for example, he, she, it and the distinction between the woman WHO is there vs. the tree WHICH is there; who and which mark humanness and non-humanness.

Often then, the term "grammatical gender" is used for systems in which there is a less of a relationship between real world characteristics and the type of nouns and pronouns. Most languages that have this arbitrariness do have some association with real world characteristics though.

In the Romance languages, there is natural gender for pronouns and adjectives that refer to humans, and some animals, based on biological sex, so in Spanish, you would say soy alto (I'm tall) if you identify as male but soy alta if you identify as female, but other nouns are assigned to either masculine or feminine with no regard for any real world characteristics, es alto (it's tall) could refer to a tree (el árbol), while es alta could refer to a mountain (la montaña).

Importantly, this system can override real world associations. Again in Spanish, living beings, especially people, are usually referred to based on their biological sex, a man would be él (he), but grammatical gender overrides this, persona is feminine, so if you say he is a good person, good person will be grammatically feminine, él es una buena persona.

So, the arbitrariness here. Why is the tree masculine and the mountain feminine in Spanish? Well, there are many possible reasons. These arbitrary genders are tied to the word and often, the gender is inherited. The system in Spanish comes from the three gender system in Latin, in the main, the gender of the word is the same as it was in Latin.

The Latin system in turn comes from the Proto-indo-european system. Now, that proto means this is a reconstructed language, we have no direct evidence of it. But it seems like this language had, originally, a gender system based on animacy. Animate nouns were in one category and inanimate nouns were in another. But what is animate and inanimate is often rooted in culture, is a river animate? What about a tree?

The animate gender eventually split into masculine and feminine. The way this happened is a bit complicated and not completely understood, but basically some endings became associated into a new gender and then, that became associated with biological sex. That could have happened because of any number of reasons, maybe the word for woman happened to have the ending associated with the new feminine gender and then this association with the noun type was expanded to refer to natural gender.

Endings are very important for the Indo-European gender systems. English inherited the same three gender system that Latin did. But it's been entirely lost primarily because phonological changes removed many word endings that maintained those distinctions.

The Romance languages almost entirely lost the neuter gender similarly because it was not distinct in ending from the other genders. Instead, neuter nouns were reassigned based on their ending. For example, the plural of the word folium (leaf) which was neuter in Latin was folia, this -a ending became associated with feminine singular so the word was grouped in with feminine nouns and reanalyzed as singular, it's the source of French la feuille and Spanish la hoja, both feminine.

Other neuter nouns seemed to have masculine endings, so they just became masculine. There's nothing particularly masculine or feminine about these nouns, they just happen to have an ending that's associated with that noun category, so they naturally fall into that category.

In Swedish and Danish, which also inherited the same three gender system, sound changes actually made masculine and feminine endings similar and they collapsed into one group, a common group that contrasts with the neuter group. The same process is currently happening in Dutch, actually and most speakers only use a common and neuter gender.

Remember that originally the masculine and feminine genders come from an animate gender, and neuter comes from an older inanimate. So there is still a tendency for living things, animate things, to fall into the common gender and for the neuter gender to be primarily inanimate.

But this is always superseded by the notion of these categories as patterns, in Indo-European languages, usually marked by endings, so there are many many exceptions, often because semantic drift has changed the meaning of the word.

For example, the Swedish word for an animal, ett djur, is neuter, it's cognate with English deer, which also used to mean animal but was restricted in meaning and replaced by Latinate loans like beast and animal. Why wouldn't an animal be considered animate and thus common?

Well, if you trace back the source to Proto-indo-european, its root originally meant breath and likely stemmed from the word for smoke or something similar. A concept that could clearly be seen as inanimate, so over millenia, from smoke, to breath, to breathing thing, to living thing, to animal, all the while maintaining a pattern that was originally associated with inanimacy and then became typical of the neuter gender.

So any given word in a language with gender might be assigned to a particular gender because it has an ending associated with that gender or the meaning of the word has changed over time. The origin of the system itself might be rooted in something natural, maybe animacy as in early Proto-indo-european, or as in other language families, certain materials or uses or any other categorization. Or the system might arise itself from endings, certain endings form their own group, as the feminine gender seems to have in later Proto-indo-european, later picking up an association with a natural characteristic, in this case, biological sex.

Now, with this in mind, I want to tackle your hypothetical. You don't have to go 10k years in the past, people encounter new concepts and objects all the time. But names aren't random, we don't just put together a string of sounds.

In 2022 or 4000 BC, if you find something new, you'll name it something logical. If it looks like a rock, maybe something using the word for rock, and the gender for that. Or a diminutive, which might have its own gender, German -chen always makes a neuter noun, hence why Mädchen (girl) is neuter, it literally means maid-kin. The -chen suffix actually stems from a way to form adjectives from nouns, which is a common source for diminutives, like English -y in both healthy from health and Bobby from Bob,.

If it is a wholly new word for some reason, then if it sounds like it fits a pattern, it will fall into that pattern. If you invent a word in Spanish that ends in -a, speakers will take it to be feminine. hamaca (hammock) from the Taino language is feminine probably because of the ending.

If the word isn't marked specifically with a gender pattern, it might vary in gender. Spanish el árbol, for example, isn't marked for masculine or feminine and it in fact comes from a feminine noun in Classical Latin, which shifted at some point in Late Latin. In Italian, it's actually picked up a masculine ending, albero, to match this gender. And you can find both el mar and la mar as well as el final and la final.

Or it might be based on an association for the word. A type of table might take the gender that table has. But this can also lead to disagreements about gender.

For example, when the word COVID was introduced into Spanish and French, it was often perceived to be masculine because the word virus in both languages is masculine. Official language regulators preferred a feminine form because it's the name of the disease, and the primary word for disease in both languages is feminine, la enfermedad and la maladie respectively. So nowadays, you often find both.

So new words are assigned in similar ways to old words. Either because of an association with an existing category (masculine COVID because viruses are masculine), they sound a particular way (feminine hamaca because it ends in -a) or if it's made from native compounds, based on the gender of those compounds, neuter Mädchen because of neuter -chen.

Because this is a historical linguistics question, it is allowable here, but you may also want to try /r/linguistics.