RE the guy escaping through the Wall back to Winterfell in the pilot (before he's beheaded by Ned Stark):

It's mentioned in episode 4 (or 3?) that there are tunnels underneath the Wall that the Night's Watch use to get back and forth, as opposed to going over top. In fact, in the prologue to episode 1, you can see the guy that gets beheaded and the other two walking through one of these tunnels.

Presumably there are no guards at the ends of these tunnels, so a member of the Night's Watch can go through them and desert without anyone knowing.

Though it seems like the horse riders did know that he deserted, so they probably saw him running away from atop the Wall.

This is all conjecture on my part, by the way. Someone who's read the books might be able to provide more information.

And skyjedi, according the friends of mine who have read the books and seen the series (what's aired of it so far), Game of Thrones is far more faithful to the book than the LOTR films were to Tolkien's books.