The surviving Black Brother, Gared, from the prologue of A Game of Thrones is apparently the deserter who is beheaded in the beginning of the book.
But how did he manage to get to Winterfell from the other side of The Wall? Or did the show throw me off track and in the book there weren't any survivors, so the deserter is someone else?
The Wall is there primarily to keep the wildlings from crossing in large numbers (in current times, at least). It has never stopped individuals from crossing, if they know where to look.
In the books, it is mentioned later on in the series that there are many fortifications along the Wall, but over time many of them have become disused and abandoned. Coverage is not what it used to be.
Keep in mind that even the Direwolf made it from beyond the Wall, so climbing over the top is clearly not the only option.
In A Storm of Swords it is mentioned that there are four ways to get from one side of the Wall to the other (aside from being let through the gates by the Black Brothers): you can climb it, attempt to cross the Bay of Seals by boat, descend into the ravines to the west of the Shadow Tower, or use the array of tunnels underneath (such as Gorne's Way).
Edit: I just re-read the part where Bran, Hodor and the Reeds cross the Wall under the Nightfort. There is a gate that is accessible to any sworn Brother, and it is certainly possible that the deserter somehow either knew of this, or found it.
In the TV show, the younger ranger survives, but in the book Gared the older ranger survives. Since the execution scene is from Bran's perspective and Bran is less concerned with who the ranger is, we are not given his name but the descriptions match up enough to show that it is Gared.
Prologue
Gared did not rise to the bait. He was an old man, past fifty, and he had seen the lordlings come and go.
...
Gared had spent forty years in the Night's Watch, man and boy, and he was not accustomed to being made light of.
...
"I've had the cold in me too, lordling." Gared pulled back his hood, giving Ser Weymar a good long look at the stumps where his ears had been. "Two ears, three toes, and the little finger off my left hand."
...
Gared glared at the lordling, the scares around his ear holes flushed red with anger where Master Aemon had cut the ears away.
At the end of the prologue, Royce is dead and Will is dying. Gared was waiting with the horses so it is more possible that he survived than the others.
Bran
But the man they found bound hand and foot to the holdfast wall awaiting the king's justice was old and scrawny, not much taller than Robb. He had lost both ears and a finger to frostbite, and he dressed all in black, the same as a brother of the Night's Watch, except that his furs were ragged and greasy.
Actually, we don't know that he didn't report back to his Wall station and then desert southward at the first possible opportunity
The Wall hasn't been fully manned in years. And individual Wildlings have been known to sneak past every now and then. Some examples from later in the books:
Osha and her band made it as far as Winterfell. Mance Rayder did one better. He slipped through and attended the Stark feast for King Robert. And Jon Snow spent some time with a raider party that slipped through and were planning on mischief south of the Wall.
I would like to point out that the wall does NOT fully block the North. From Eastwatch, as mentioned, Wildlings slip by in boats. In the West, the Wall ends at the Shadow Tower, which you will notice is not at the coast. In later books, there are attempts to "force the Bridge of Skulls" which presumably bypasses the Shadow Tower and the Wall. It is also mentioned that Wildlings slip through the hills of the western side from time to time. The Fist of the First Men (a location from later) is near the Western part of the Wall, it is possible, if not likely that Will/Gared (especially Gared as a seasoned and veteran ranger) would slip past the Shadow Tower in the West.
The deserter was definitely the same person as he is described as having missing ears and fingers but I thought he had grabbed the broken sword and was going back to report to someone at The Wall. He must have deserted after that.
I'm actually reading the first book of A song of ice and fire and I found this:
"The Lord Commander took no notice of the irritating bird. "Gared was near as old as I am and longer on the Wall," he went on, "yet it would seem he forswore himself and fled. I should never have believed it, not of him, but Lord Eddard sent me his head from Winterfell. Of Royce no word. One deserter and two men lost, and now Ben Stark too has gone missing"
Tyrion - A Game of Thrones
So, according to Beofett the deserter is Gared.
I've only seen the show, haven't read any of the books. But between that scene and the scene with the dead dire wolf, they were establishing that The Wall isn't providing 100% protection.
The survivor is named differently in show and books.
Other than that, the survivor is most definitely Gared.
The commander of the party, Ser Waymar Royce had ordered Gared to stay behind with the horses while he went ahead with Will.
From AGOT, Prologue:
“If I need instruction, I will ask for it,” the young lord said. “Gared, stay here. Guard the horses.”
Ser Waymar himself got killed in a fight with the others, Will observed his corpse:
Royce’s body lay face down in the snow, one arm outflung. The thick sable cloak had been slashed in a dozen places. Lying dead like that, you saw how young he was. A boy.
Then Will saw Royce rise up again and throttle him to plausibly death:
Will rose. Ser Waymar Royce stood over him.
His fine clothes were a tatter, his face a ruin. A shard from his sword transfixed the blind white pupil of his left eye.
The right eye was open. The pupil burned blue. It saw.
The broken sword fell from nerveless fingers. Will closed his eyes to pray. Long, elegant hands brushed his cheek, then tightened around his throat. They were gloved in the finest moleskin and sticky with blood, yet the touch was icy cold.
So it is clear from here that out of the three members of the party, two got killed in the prologue. Which leaves us with Gared.
In AGOT, Tyrion III, Lord Commander confirms that it was Gared who got executed by Eddard Stark:
The Lord Commander took no notice of the irritating bird. "Gared was near as old as I am and longer on the Wall," he went on, "yet it would seem he forswore himself and fled. I should never have believed it, not of him, but Lord Eddard sent me his head from Winterfell. Of Royce, there is no word. One deserter and two men lost, and now Ben Stark too has gone missing." He sighed deeply.
Even Craster knew that Gared had been executed. From ACOK, Jon III:
Lord Mormont said, "Ben was searching for Ser Waymar Royce, who'd vanished with Gared and young Will."
"Aye, those three I recall. The lordling no older than one of these pups. Too proud to sleep under my roof, him in his sable cloak and black steel. My wives give him big cow eyes all the same." He turned his squint on the nearest of the women. "Gared says they were chasing raiders. I told him, with a commander that green, best not catch 'em. Gared wasn't half-bad, for a crow. Had less ears than me, that one. The 'bite took 'em, same as mine." Craster laughed. "Now I hear he got no head neither. The 'bite do that too?"
See my previous answer here which discusses all the ways wall can be defeated in detail.
Being veteran member of Night's Watch, he (Will in Show and Gared in books) should have been able to use the magical black gate in Night Fort however it is not known if he knew about the gate. Alternatively he could have just used any of the methods listed in my other answer, depending on tools he had with him and the location he was at. It is not specifically mentioned.
