alt Hacker NewsIn Spanish, native speakers typically learn (implicitly) or memorize (explicitly) the gendered article along with the noun, so instead of thinking "hmm, let me remember the gender of mapa" they'll just have that noun stored internally as "el mapa". It's still a matter of memorization (at least for words whose gender violates the typically spelling heuristics), but it's not really conceived of as memorizing the word and then separately memorizing its gender. And of course, there will always be rare or specialized terms that a native speaker might recognize but confidently know the gender. This is especially true for the small set of nouns whose gender varies by region or context.
Except in Spanish, gender is pretty easily determined from the word ending 99.9% of the time unless it's a Greek neuter, and there are only a few of those.
In French, it's common for people not to remember the gender of uncommon words. IIRC, there is or was a radio program in France that would call up random people and offer them a prize if they could guess the genders of a list of 10 words correctly.