tl;dr: So far, we do not have any solid information about where The Others (which are called White Walkers on TV, to avoid confusion with the general term "others") came from. We also don't know a whole lot about the Night's King, but he definitely was not the first White Walker, since they pre-date the Night's Watch.
Unfortunately, there's no truly reliable records of anything that happened during that time, as written history did not begin until 6,000 BC with the arrival of the Andals. Instead, history was passed down by word of mouth, though stories, which became myths and legends. This means that our most "reliable" source of information comes from people like Old Nan. While Nan does tend to be right about a lot of things, her information is still anecdotal and heresay, and she's more interested in having good stories than good facts, so we should be properly skeptical of what she has to say.
The Others and The Long Night
The Others first appeared sometime around 8,000 BC (Before Conquest -- before the start of Aegon I Targaryen's reign), which puts it right in the middle of the Age of Heroes. (For reference, the First Men arrived on Westeros sometime around 12,000 BC, and made peace with the Children of the Forest around 10,000 BC). At that time, the First Men and the Children were at peace, and many of the Great Houses were just getting started. All of the legendary ancestors of the current houses lived during this period - Bran the Builder, Lann the Clever, the Grey King of Iron Islands, etc.
About 2,000 years after The Pact was signed between the First Men and the Children, Westeros underwent an unprecedented long winter, putting Westeros in pretty bad condition. In the middle of this winter, there was an even worse catastrophe: the Long Night, in which the sun did not rise for an entire generation (which likely means at least 20 years). It was during this Long Night that the Others appeared, from the extreme furthest reaches of the North of Westeros.
The climate in the far, far North is akin to that of Antarctica, and was thought to be completely unpopulated. Thus, the Others appearance was a complete surprise. Again, we don't know for sure, but it seems as if they were something brand new to Westeros, as the Children of the Forest did not know how to defeat them. The Others pushed down into the south of Westeros before their weakness -- obsidian -- was discovered, and they were pushed back.
The Night's Watch and The Wall
The Nights Watch was formed during this time, specifically to fight the Others. (This part of the history is commemorated in a song, "The Night That Ended", which is sung in the North and referenced a few times, though since this isn't Tolkien we don't get any lyrics :( ). The Watch fought the Others back and ultimately defeated them in the Battle for the Dawn.
After that, Bran the Builder and his allies built The Wall, again specifically to fight back against The Others. It was meant to ensure that they could never sneak up on Westeros again. The Night's Watch, being the ones that knew how to fight them off, were set to man The Wall.
Again, there are no written histories of anything during that time, so we don't know the names of the commanders. Only the ones who did something worthy of song or story are remembered.
The Night's King and his Bride
The Night's King was the thirteenth person elected as the Lord Commander of the Watch. According to his legend, he forsook his Oath, took a bride, and raised the Night's Watch in rebellion against Westeros. His Bride is described as:
with skin as white as the moon and eyes like blue stars
Given this description, it's obvious why many fans assume she is an Other, though the maesters in-universe apparently think her description matches that of the men and women of the Barrowlands. In either case, we know almost nothing more about them personally. We know that he was eventually defeated by the King in the North and the King Beyond the Wall. We know that he was ultimately discovered to have been making sacrifices to The Others (much like Craster), and that every possible record of his or her name was destroyed, and subsequent stories and songs only use his sobriquet.
More to Come
Martin has been very intentionally coy about revealing information on things that are magical in origin. (e.g. See The Bridge on the River Rhoyne for a case where he cut something out because it was potentially "too magical.") However, he has also said that he will eventually reveal much of this eventually, towards the end of the series. He's also said we'll learn more about the Others (though he hasn't promised we'll learn where they came from) in the next novel.
Martin has implied that the screwy weather in Westeros is magical in nature, and the Others are also clearly supernatural. They also seem to be extremely closely related -- both times they appeared was during what was supposedly an extremely harsh Winter. So, it's very likely their origins are tied closely together, and we will find out about them both at the same time.
