It is one of those mysteries that several major language families all do it in a similar way. From Ancient Egyptian to Latin to small languages spoken in New Guinea, there is a common pattern of grammatical markings associated with indicating a person or animal's sex, ending up used to indicate noun classes and govern alignment/agreement patterns.
But why? Well, in languages like Latin with fairly free word order, noun classes and the associated agreement help indicate what goes with what. My take is that it's almost like a form of forwards error correction or type annotation. The way it arises like that doesn't seem too far-fetched.
The persistence is tricky though. Normally a feature in a language that isn't productive is going to get worn down by sound changes, etc. and eventually lost. But grammatical gender rarely gets lost. (English is a major exception as an Indo-European language here.) Even as Latin transformed over thousands of years into French, with grammar and phonology that are basically unrecognizable, a basic gender system persists in the language. I can only assume its error correcting/type annotating properties are still useful even in modern French?