Magnetoception is a general description for the ability to detect the Earth's magnetic field and use it for navigation. To quote the 2010 review from which the image above is taken:
...The magnetic sense must therefore be addressed as an additional and stand-alone sense, besides vision, hearing, olfaction, taste, electroreception and mechanosensation.
Experimental studies of magnetic field guided behavior have focused on migratory animals like birds (for review: , reptiles  or fish ), but evidence also exists from experiments with mammals (mole rat ; bat ) and several invertebrate species (crustaceans ; honey bees ; cockroaches ; marine molluscs ). Despite the overwhelming behavioral evidence, the molecular, physiological, and cognitive mechanisms enabling animals to sense and extract useful information from the geomagnetic field remain obscure.
The cells shown above detect magnetic fields in the upper beaks of birds by having particles of iron in the dendrites (receptive areas) of nerves, and return sensations by the trigeminal nerve that relays sensation from the face. Human magnetic sense has been proposed to be mediated by CRY2, a cryptochrome in the eye (optical pigment like protein) that senses magnetism a different way using light.
"Mitochondrial Eve" did not actually live alone, but was among at least tens of thousands. Her children never needed to resort to Noah's Ark Family Hour to produce the next generation. She is merely the lucky winner - chosen long after the fact - whose mitochondria won out in a long game of evolution. But in the spirit of the question, her offspring still suffered a major trauma - the Laschamp event 42,000 years ago, which probably would have been a geomagnetic reversal except the coin came up heads twice in a row. "Auroras blazed near the equator", and magnetic perception became if anything a disadvantage.
For this story, let's suppose that ancient humans from H. erectus onward, being long distance runners, had been busily evolving a magnetic sense from some weak vestigial mechanisms. By 42k years ago, many humans could easily navigate by magnetic fields. However, the talent remained rare, because once a tribe had a couple of shamans who could guide them on long trips, the selective advantage for further perfection of the mechanism weakened. Then the Laschamp Event hit and the shamans lost their magic powers for 250 years. The other humans rebelled against the shamans' privileges, put forward their own chiefs, and held witch hunts for centuries even after the geomagnetic field had gotten back to normal. The genetic basis of the sense involves multiple genes, and people with the right forms of all of them are rare, so there are only a very few oddballs here and there claiming to have this talent, who are dismissed by the rest as charlatans.