In the beginning
Navigators were created through genetic engineering during the Dark Age of Technology when humanity realized that a special kind of psyker could find his way through the Warp better than any piece of technology. Navigators, with the third eye in the middle of their forehead, can look directly upon the Warp and perceive its currents, allowing longer and safer journeys through the very heart of the Warp. It's somewhat analogous to a sailing ship cutting right across the sea rather than hugging the coastline (although when you read the fluff on Tau ships it gets more confusing). Since the Astronomican didn't exist at the time, we can only assume the humans of the dark Age of Technology had invented artificial warp beacons and didn't need such a big lighthouse and/or only proceeded with very short jumps. After the Age of Strife the beacon network was destroyed until Big E managed to construct his own on Terra.
The genes that make a Navigator are recessive (which leads to some suspicion Big.E. had a hand in their creation). If a Navigator mates with a regular human, all their kids will be normal. They thus had to
form an endogamous caste resort to lots and lots of in-breeding, giving rise to the oft-told Imperial Navy joke, "How do you tell the difference between the Navigator's sister and father?" "You don't, they're the same person!" [sound of laughing followed by a summary execution] However, their genome is not stable like abhumans, and are thus mutants. While their bodies conform to the holy human form while they are younger, prolonged exposure to the Warp, coupled with unstable genetics, will result in the Navigator developing mutations that deviate too far from the human form to be publicly accepted. There is not uniformity to the mutations, but depends on the Navigator. Usually they look like frogs, though. These members are known as the Elders, who actually form the leadership of a House. To maintain a public appearance, the Elders select the patriarch or matriarch of the House, known as either a Novator or Celestarch. In the earlier days of the Imperium, these grand poobahs used to accompany expeditions and were so talented they could guide fleets through the most tempestuous warp storm. Nowadays they're too precious to waste on anything dangerous, save for inter family murder-bickering on Terra.
When the Emperor set about uniting Terra and preparing to go to the stars, he was presented with a bit of a problem. Part of the Imperial Truth he was spouting maintained that humans were destined to rule the stars, and he was still centuries away from getting the Webway project up and running. Simply put, the Emperor needed the Navigators, even if he was fully aware of how "age before beauty" was a horrible lie to the Navigators. Deciding "fuck it, we need space travel", the Big.E. went to the Paternova (the leader of the Navis Nobilite) and made an agreement: "Keep to yourselves in your part of Terra and your mutant Elders out of sight, and we'll pay you to fly our starships and protect you from some of the more zealous anti-mutant groups". The Paternova agreed, and thus humans can fly through the Warp, using the Astronomican to navigate.
Who knows what the Emperor would have done with them had he completed his secret Webway project. It was pretty clear that he hated any psyker who wasn't absolutely necessary. (
One time he even told his Space Marines to get rid of their Librarians. That was only to put a leash on Magnus before he or his ilk would befriend some warplings during their magic-research. Too bad it backfired spectacularly.) Anyway, judging from how the Thunder Warriors ended, the answer is probably enforced retirement at gunpoint once their usefulness to the Imperium would be at an end.
In the 41st millennium, the Navigators are part of the High Lords of Terra, represented by the Paternoval Envoy. A lot of people in the Administratum, the Ecclesiarchy, and the Inquisition aren't too thrilled with this, but they can't really do anything to the Navigators without irreparably crippling the Imperium. The more extreme ones still try to do something about it. Imperial dogma is frequently contradictory. Pointing this out is
Being psykers, Navigators are vulnerable to madness and daemonic possession. The Inquisition (about the only people who can really touch them) keeps a close eye on the Navigator Families and has destroyed more than a few who became corrupted. The Navigators try to resolve such problems internally, knowing how overboard the Inquisition likes to go. Wars between Navigator Houses are not uncommon, but are frequently done on the down low. It is a mutually agreed-upon rule that you can wipe a rival House out and no one bats a third eye, but so much as leak one photograph of their Elders and pretty much every single Navigator in the Imperium will turn on the transgressor ASAP. From birth the Navigators are told just how fragile the whole charade about their mutation into a frog-fish hybrid is and it's very much drilled into them not to tell anyone about their visit to Granny in the basement.