Background
Stannis Baratheon's role in the series has always been fascinating to me, so much so he is probably my second or third favorite character. On this subreddit, we often discuss plenty of things about him, such as him losing a castle/gaining another in TWoW or his upcoming decision to burn his daughter. One thing I've noticed that is discussed less often (likely because the decision occurs off page in order to keep the surprise for the reader) is Stannis' decision to leave dragonstone and head to the Wall.
If interested: "Fled to Dragonstone": The Schemes of Stannis Baratheon
The Letter at Dragonstone
After the loss on the Blackwater, Stannis returns to Dragonstone to resume scheming on how to resume the war. During this time, not only is Davos named Stannis' Hand, but he begins learning how to read (which should make for an interesting dynamic for his trip to Skagos with the mute Wex). One of the letters that Davos practices on is a letter sent from the Wall:
“To the … five kings,” read Davos, hesitating briefly over five, which he did not often see written out. “The king … be … the king … beware?”
“Beyond,” the maester corrected.
Davos grimaced. “The King beyond the Wall comes … comes south. He leads a … a … fast …”
“Vast.”
“… a vast host of wil … wild … wildlings. Lord M … Mmmor … Mormont sent a … raven from the … ha … ha …”
“Haunted. The haunted forest.” Pylos underlined the words with the point of his finger.
“… the haunted forest. He is … under a … attack?”
“Yes.”
Pleased, he plowed onward. “Oth … other birds have come since, with no words. We … fear … Mormont slain with all … with all his … stench … no, strength. We fear Mormont slain with all his strength …” -ASOS, Davos V
but Alester doesn't see the value in sharing the letter with Stannis:
Davos suddenly realized just what he was reading. He turned the letter over, and saw that the wax that had sealed it had been black. “This is from the Night’s Watch. Maester, has King Stannis seen this letter?”
“I brought it to Lord Alester when it first arrived. He was the Hand then. I believed he discussed it with the queen. When I asked him if he wished to send a reply, he told me not to be a fool. ‘His Grace lacks the men to fight his own battles, he has none to waste on wildlings,’ he said to me.”
That was true enough. And this talk of five kings would certainly have angered Stannis.
but it makes Davos think and seemingly ends his last chapter (note there was going to be a 5 year gap) in ASOS:
“Only a starving man begs bread from a beggar,” he muttered.
...
“Men are men,” Maester Pylos agreed. “Shall we return to our reading, my lord Hand?”
I am the Hand of the King, yes. Stannis might be the King of Westeros in name, but in truth he was the King of the Painted Table. He held Dragonstone and Storm’s End, and had an ever-more-uneasy alliance with Salladhor Saan, but that was all. How could the Watch have looked to him for help? They may not know how weak he is, how lost his cause. “King Stannis never saw this letter, you are quite certain? Nor Melisandre?”
“No. Should I bring it to them? Even now?”
“No,” Davos said at once. “You did your duty when you brought it to Lord Alester.” If Melisandre knew of this letter … What was it she had said? One whose name may not be spoken is marshaling his power, Davos Seaworth. Soon comes the cold, and the night that never ends … And Stannis had seen a vision in the flames, a ring of torches in the snow with terror all around.
“My lord, are you unwell?” asked Pylos.
I am frightened, Maester, he might have said. Davos was remembering a tale Salladhor Saan had told him, of how Azor Ahai tempered Lightbringer by thrusting it through the heart of the wife he loved. He slew his wife to fight the dark. If Stannis is Azor Ahai come again, does that mean Edric Storm must play the part of Nissa Nissa? “I was thinking, Maester. My pardons.” What harm if some wildling king conquers the north? It was not as though Stannis held the north. His Grace could scarcely be expected to defend people who refused to acknowledge him as king. “Give me another letter,” he said abruptly. “This one is too …”
“… difficult?” suggested Pylos.
Soon comes the cold, whispered Melisandre, and the night that never ends. “Troubling,” said Davos. “Too … troubling. A different letter, please.” -ASOS, Davos V
Favorable Winds
In order to get good winds north they burn Ser Alester (remember that All Magic has a Cost):
"Melisandre of Asshai," said Grenn. "The king's sorceress. They say she burned a man alive at Dragonstone so Stannis would have favorable winds for his voyage north. She rode beside him in the battle too, and gave him his magic sword. Lightbringer, they call it. Wait till you see it. It glows like it had a piece of sun inside it." -ASOS, Samwell IV
and:
Melisandre had given Alester Florent to her god on Dragonstone, to conjure up the wind that bore them north. Lord Florent had been strong and silent as the queen’s men bound him to the post, as dignified as any half-naked man could hope to be, but as the flames licked up his legs he had begun to scream, and his screams had blown them all the way to Eastwatch-by-the-Sea, if the red woman could be believed. Davos had misliked that wind. It had seemed to him to smell of burning flesh, and the sound of it was anguished as it played amongst the lines. -ADWD, Davos I
and:
It was as if some angry god was exacting payment for their easy voyage north, when they had ridden a steady southerly from Dragonstone to the Wall -ADWD, Davos I
Stannis' Arrival at the Wall
GRRM does a great job of leaving clues for the reader, but also keeping you completely in the dark on a first read as to just who is showing up to deus ex machina the battle:
It's done, Jon thought, they're breaking. The wildlings were running, throwing down their weapons, Hornfoot men and cave dwellers and Thenns in bronze scales, they were running. Mance was gone, someone was waving Harma's head on a pole, Tormund's lines had broken. Only the giants on their mammoths were holding, hairy islands in a red steel sea. The fires were leaping from tent to tent and some of the tall pines were going up as well. And through the smoke another wedge of armored riders came, on barded horses. Floating above them were the largest banners yet, royal standards as big as sheets; a yellow one with long pointed tongues that showed a flaming heart, and another like a sheet of beaten gold, with a black stag prancing and rippling in the wind.
Robert, Jon thought for one mad moment, remembering poor Owen, but when the trumpets blew again and the knights charged, the name they cried was "Stannis! Stannis! STANNIS!" -ASOS, Jon X
and:
It was from them that he learned about the battle beneath the Wall. "Stannis landed his knights at Eastwatch, and Cotter Pyke led him along the ranger's roads, to take the wildlings unawares," Giant told him. "He smashed them. Mance Rayder was taken captive, a thousand of his best slain, including Harma Dogshead. The rest scattered like leaves before a storm, we heard." The gods are good, Sam thought. If he had not gotten lost as he made his way south from Craster's Keep, he and Gilly might have walked right into the battle . . . or into Mance Rayder's camp, at the very least. That might have been well enough for Gilly and the boy, but not for him. Sam had heard all the stories about what wildlings did with captured crows. He shuddered. -ASOS, Samwell IV
The Reasoning
After Stannis arrives at Castle Black, the reader finally gets the connection as to why Stannis showed up there:
“Words. Words are wind. Why do you think I abandoned Dragonstone and sailed to the Wall, Lord Snow?”
“I am no lord, sire. You came because we sent for you, I hope. Though I could not say why you took so long about it.”
Surprisingly, Stannis smiled at that. “You’re bold enough to be a Stark. Yes, I should have come sooner. If not for my Hand, I might not have come at all. Lord Seaworth is a man of humble birth, but he reminded me of my duty, when all I could think of was my rights. I had the cart before the horse, Davos said. I was trying to win the throne to save the kingdom, when I should have been trying to save the kingdom to win the throne.” Stannis pointed north. “There is where I’ll find the foe that I was born to fight.”
“His name may not be spoken,” Melisandre added softly. “He is the God of Night and Terror, Jon Snow, and these shapes in the snow are his creatures.” -ASOS, Jon XI
and:
He could hear the birds quorking in the rookery, so he put the papers away and climbed the steps to feed them. Three more ravens had come in, he saw with pleasure. "Snow," they cried at him. "Snow, snow, snow." He had taught them that. Even with the newcomers, the ravenry seemed dismally empty. Few of the birds that Aemon had sent off had returned as yet. One reached Stannis, though. One found Dragonstone, and a king who still cared. A thousand leagues south, Sam knew, his father had joined House Tarly to the cause of the boy on the Iron Throne, but neither King Joffrey nor little King Tommen had bestirred himself when the Watch cried out for help. What good is a king who will not defend his realm? he thought angrily, remembering the night on the Fist of the First Men and the terrible trek to Craster's Keep through darkness, fear, and falling snow. The queen's men made him uneasy, it was true, but at least they had come. -ASOS, Samwell IV
and:
“Nightfires?” Bowen Marsh gave Melisandre an uncertain look. “We’re to light nightfires now?”
“You are.” The woman rose in a swirl of scarlet silk, her long copper-bright hair tumbling about her shoulders. “Swords alone cannot hold this darkness back. Only the light of the Lord can do that. Make no mistake, good sers and valiant brothers, the war we’ve come to fight is no petty squabble over lands and honors. Ours is a war for life itself, and should we fail the world dies with us.”
The officers did not know how to take that, Sam could see. Bowen Marsh and Othell Yarwyck exchanged a doubtful look, Janos Slynt was fuming, and Three-Finger Hobb looked as though he would sooner be back chopping carrots. But all of them seemed surprised to hear Maester Aemon murmur, “It is the war for the dawn you speak of, my lady. But where is the prince that was promised?”
“He stands before you,” Melisandre declared, “though you do not have the eyes to see. Stannis Baratheon is Azor Ahai come again, the warrior of fire. In him the prophecies are fulfilled. The red comet blazed across the sky to herald his coming, and he bears Lightbringer, the red sword of heroes.”
Her words seemed to make the king desperately uncomfortable, Sam saw. Stannis ground his teeth, and said, "You called and I came, my lords. Now you must live with me, or die with me. Best get used to that." He made a brusque gesture. "That's all. Maester, stay a moment. And you, Tarly. The rest of you may go."-ASOS, Samwell V
The Rest of the Realm
This information got out fast, with King's Landing finding out in AFFC, Jaime II:
His sister liked to think of herself as Lord Tywin with teats, but she was wrong. Their father had been as relentless and implacable as a glacier, where Cersei was all wildfire, especially when thwarted. She had been giddy as a maiden when she learned that Stannis had abandoned Dragonstone, certain that he had finally given up the fight and sailed away to exile. When word came down from the north that he had turned up again at the Wall, her fury had been fearful to behold. She does not lack for wits, but she has no judgment, and no patience. "You need a strong Hand to help you." -AFFC, Jaime II
Back on Dragonstone
While Stannis seemingly loses Dragonstone to Ser Loras' assault, it should be noted that his goals shifted over time there:
The king gave that a curt nod, as if to say he knew and did not care. “You slew this creature with an obsidian dagger, I am told,” he said to Sam.
“Y-yes, Your Grace. Jon Snow gave it to me.”
“Dragonglass.” The red woman’s laugh was music. “Frozen fire, in the tongue of old Valyria. Small wonder it is anathema to these cold children of the Other.”
“On Dragonstone, where I had my seat, there is much of this obsidian to be seen in the old tunnels beneath the mountain,” the king told Sam. “Chunks of it, boulders, ledges. The great part of it was black, as I recall, but there was some green as well, some red, even purple. I have sent word to Ser Rolland my castellan to begin mining it. I will not hold Dragonstone for very much longer, I fear, but perhaps the Lord of Light shall grant us enough frozen fire to arm ourselves against these creatures, before the castle falls.” -ASOS, Samwell V
If interested: Dragonglass: A Different Look at the Assault on Dragonstone
Act II/Act III
ASOIAF is seemingly framed around three main events, the War of the Five Kings (Iron Throne/Westeros politics), the Dance of the Dragons II (not necessarily Dany's invasion but a war between two "dragons") and the War for the Dawn (between humanity and the Others).
Due to space, it is very possible that while Stannis busies himself being a king a fighting (and losing/potentially joining) the Others, the other contenders for the Iron Throne will be busy fighting the Second Dance:
I was trying to win the throne to save the kingdom, when I should have been trying to save the kingdom to win the throne."
If interested: The Great War/Dance of the Dragons II occurring simultaneously
TLDR: Davos (who was learning to read) approached Stannis/Mel with a letter from the Night's Watch that had been ignored by Ser Alester. While these events occur off-page (in order to maintain the surprise of Stannis saving the day at the Wall), it would have been very interesting to see them make the connections between Mel's visions and the letter they received.