"Much as I admire Tolkien, and I do admire Tolkien — he’s been a huge influence on me, and his Lord of the Rings is the mountain that leans over every other fantasy written since and shaped all of modern fantasy — there are things about it, the whole concept of the Dark Lord, and good guys battling bad guys, Good versus Evil, while brilliantly handled in Tolkien, in the hands of many Tolkien successors, it has become kind of a cartoon. We don’t need any more Dark Lords, we don’t need any more, ‘Here are the good guys, they’re in white, there are the bad guys, they’re in black. And also, they’re really ugly, the bad guys." **George R. R. Martin, Assignment X Interview, 2011
What is known of the Others?
The creatures themselves are encountered in the prologue, the battle at the Fist of the First Men, and when Sam kills one with a piece of Obsidian.
What else do we know about them?
Precious little. They have a language, they make things out of ice with magical properties, and they raise the dead to fight for them. We can infer a few other things from conversations about them. Tormund has quite a bit to say:
They’re never far, you know. They won’t come out by day, not when that old sun’s shining, but don’t think that means they went away. Shadows never go away. Might be you don’t see them, but they’re always clinging to your heels.
When the snows came though…snow and sleet and freezing rain, its bloody hard to find dry wood or get your kindling lit, and the cold…some nights our fires just seemed to shrivel up and die. Nights like that, you always find some dead come the morning. ‘Less they find you first.
A man can fight the dead, but when their masters come, when the white mists rise up … how do you fights a mist crow? Shadows with teeth … air so cold it hurts to breath, like a knife inside your chest … you do not know, you cannot know … can your sword cut cold?
The interesting thing here is that Tormund describes the Others as mists and shadows. He never mentions ice swords that shatter steel or camouflage armor or anything specific about their appearance.
This suggests that he, at least, hasn't had direct contact with them... unless they can take the form of mist.
Old Nan's stories are the other frequently cited source on the Others. Synopses can be found here
The story we're presented in the book through Nan's stories and various others' recountings and rumination is that several thousand years ago, following a mythological Age of Heroes, the Others came from the far North; prior to that point they were unknown.
According to the tales, the Others brought with them a night that lasted a generation (or the night brought them) and essentially wiped out civilization except for a small number of humans that somehow managed to drive them back. All we know about this retaliation and eventual victory is that it resulted in the construction of an enormous magical Wall of ice that, apparently, holds the others at bay.
Westerosi attribute this to a figure called the Last Hero, who may or may not be the same figure as Azor Ahai, an Eastern figure associated with the R'hllor faith. Azor Ahai's magic weapon may be an allegory for the process of taming dragons or creating Valyrian steel, either of which may involve human sacrifice as in the story.
However, there is another point to consider.
Melisandre, the only source we have on the Others outside tales and garbled legends passed down orally from a time so long ago there are no accurate histories of it, says the Others are demons of snow, ice, and cold, and essentially paints them as mindless servants of a single intelligence that opposes her fire god.
What if she's wrong?
An Alternate Theory
Ever since the tale of the Night's King appeared in the books, people have been speculating that it foreshadows someone turning to the side of the Others. Candidates for this include Roose Bolton and Stannis, the former for an apparent connection to magic, agelessness, and a general inhuman eeriness, the latter for his hunger for power, ruthless pragmatism, and possibility of snapping and going "dark" when it becomes clear he will never sit the Iron Throne.
The Night's King story is not a random horror tale. It's an explanation of how the war against the Others was won.
The story of the Last Hero as related by Old Nan ends with the Others closing in and the Last Hero, who is defenseless. It is never said he fought or defeated or conquered them.
We know that there has already been a peace between human and inhuman/supernatural beings in Westeros. The First Men and the Children came to terms and agreed to a peace treaty (which was later broken by the Andal invaders)
I propose that the Last Hero was not a conqueror, but a diplomat. An agreement was reached between Men and the Others. It was the Others themselves that raised the magical wall of ice, not to seal themselves off but to mark their territory and protect themselves from a dangerous source of fire magic to the south of their domain.
This pact was sealed as many agreements in the series are, with a marriage. A Stark or one of the ancestors of the Starks married the queen of the Others and reigned at the Wall, presiding jointly with his strange bride over a sort of demilitarized zone between Men and Others.
The Others, then, fulfilled their side of the agreement. They went away and left Men alone.
Men, unfortunately, did not keep up their end of the bargain. A large population of them has taken up residence on the wrong side of the Wall. They may be violating some now unknown and unremembered term of the agreement.
Could this be why Craster sacrifices his sons to the Others, and is left alone? Perhaps he simply rediscovered, by accident, part of this treaty or pact, and in fulfilling it was left in peace. We assume that the Others are doing something evil with the babies because they look and, apparently, act evil, but are they?
The Others attack the Night's Watch in force, but never the wildings. Why?
Simply put, the charter of the Watch goes both ways. They're not supposed to intervene in southern affairs, nor are they to intervene in northern affairs.
This brings me back to the Night's King. At some point, the Watch had a change in leadership and the hereditary House of the proto-Stark and his Other bride were deposed and replaced by the system of choosing. This is all remembered in the tale of the Night's King's downfall.
The Night's Watch, in the view of the Others, has broken the treaty and the Others are working to destroy them, most actively when they invade the North in the form of the Great Ranging.
The Wildings are simply herded south. The Others pick at their fringes and push them towards the Wall. The goal is not to exterminate them but to get them out. Men are no longer keeping their side of the agreement, so the Others are no longer obligated to keep theirs.
The Kings of Winter and the Dragonlords
If this theory is true, in ancient times the Starks and the Others (or the ruling family or class or whatever of the Others) were intermarried and allied. They were the Kings of Winter. Winter is Coming.
When Catelyn reflects on Ned's house worse, she's wrong. "Winter is Coming" is not a warning of hardship to come, it is a threat in the vein of Hear me Roar or a boast like Growing Strong.
The Starks have an innate connection to magic and the Earth, and the stories suggest links to the far north and the Others, hinting that the Starks have blood from beyond the Wall running through their veins.
This places them in direct opposition to the dragonlords. The Valyrians are not normal human beings. Humans generally don't have purple eyes and silver hair. They are not immune to fire but they do possess an affinity for heat, just like a Stark can freeze to death but Ned is comfortable sleeping in the nude in Winterfell. They also have some magical connection to dragons. (This is a seperate topic, but I propose that the whips and 'sorcerous horns' like Dragonbinder that Dany thinks about in her ADWD chapter came about after the magical blood of the Valyrians began to fade and they gradually lost control over their dragons. The trait was strong in the Targs who managed to escape before the subcontinent went boom, but faded with them as well as the dragons died out)
Something big is happening with magic. Typically, theorists try to trace the return of magic to either the Others returning or the dragons being reborn but both of these are effects preceded by a cause.
We have some clues to what that cause might be. Daenerys, Jon, and Robb, all magical children with the traits of their ancestors, were born roughly at the same time. Daenerys was the first succesful Targ to hatch dragons since they died out, and Jon and Robb are the first Stark wargs since... whenever they stopped being wargs.
It all comes back to Rhaegar.
The return of the Others isn't an apocalypse that must be prevented by harnessing the power of fire to drive them back. Rhaegar knew this and understood that the only way to preserve the human race is balance between Ice and Fire.
The Others will not be so forviging this time. Humans have shown they can't be trusted not to encroach on the Others' territory and play with fire magic and risk destroying the world, so the Others have come to wipe them out- not out of pure, senseless malice (the "reckless hate" of Tolkien's Sauron and orcs) but out of a drive to survive. The Others believe they're saving the world from Men who will, unchecked, destroy it.
That's where Jon comes in. Jon is Rhaegar's Song of Ice and Fire. This is why he dreams of himself sheathed in ice wielding a flaming sword. Jon has the blood of dragonriders and wargs and the blood of the Others through the Starks and the blood of the dragon (or something else) through the Targaryens. Jon's purpose and power isn't to defeat either side -the idea of one person, flaming sword and dragon or not, winning a war singlehandedly in this universe is laughably absurd- but to restore peace between them.
The Prince who was Promised is not Azor Ahai. Azor Ahai is the villain in the Prince's story, and Azor Ahai is Daenerys Targaryen. The purpose of Rhaegar's prophecy and "abduction" of Lyanna was, in part, to prevent his own sister from destroying the world, by passing kingship to his child of ice and fire instead of to her.
All of this was foretold in prophecy. Who says the Others don't have prophecy, too?
What woke the Others?
Assuming that they aren't mindless destroyers but an actual culture, what would bring the Others south? Could it be...
The decline of the Night's Watch
The murder of the Stark lord and his heir by the Targaryen king?
Their own prophecy of dragons returning to destroy them?
We don't know how long the Others were active or how quickly they move or organize themselves. Immortal beings, if they are immortal or very long lived, probably work on a different time scale. Waymar Royce and his party were probably not the first to encounter them, just the first time a survivor carried word South. In fact, the Others may have let Gared live as a final warning to the Night's Watch and the realms of men. Stay out, or we're coming.
We do know that Mance Rayder started gathering the wildings together to get the hell out of Dodge well before the encounter in the prologue, suggesting the Others were active well before that.
How will it end?
An epic battle between the forces of Men and the Others that ends in their total defeat and banishment from the world and a new era of peace and balanced seasons just doesn't fit with the story as told.
If I'm right, the Others are not so different from Men, and the greater conflict not so different from the smaller one. Pacts were made, backstabbing and broken oaths occurred, and now there's war.
It will end the way it did the first time, in an uneasy truce brokered by Jon, rather than a smashing victory over cold and evil by Daenerys. The Others may even ally with Men to destroy the threat of the Targaryens and their dragons before retreating north again, satisfied that Men will honor their agreement for now.
In the house of the Undying Dany has a vision of a blue rose growing from the wall. While obviously forshadowing that Lyanna's son Jon is present at the Wall, there's a second layer to this that suggests a rebirth of the Stark line on the Wall; the same imagery is used in the story of Bael the Bard.
Jon will become King on the Wall and to seal the peace, take an Other to bride, as did the Night's King of old. Not an easy or perfect or permanent peace, just a peace.
tl:dr: The Others are moving south because Men violated an ancient pact with them. The Night's King story is an account of how the War for the Dawn ended, in a peace sealed by marriage. Daenerys and her dragons are a dangerous force of chaos that threatens to destabilized the world, and the Others are hostile towards Men because of their betrayal of the Night's King and overthrow of his line, their incursion into the Other's agreed on terrritory, and the danger the Targs and their fire magic pose to the Others and the world at large. Rhaegar fathered a son by Lyanna to unite the blood of the dragonriders and the Other-kin, whether he knew it or not. Jon is that son and will bring peace between the Others and the realms of men.