All other answers (Especially Shevliaskovic's and Mooz's) are great. But I can't help but notice how some of your questions remain unanswered.
So in order to complement the already existing answers:
Why did it have to be Lord Eddard who executed Gared?
That's true. He could have gotten any of his men or vassals to do the deed.
However, Eddard Stark is a Northman and blood of the first men runs through his vein. The First Men do not get Headsmen and carry out their punishments themselves. They believe that if the man who pronounces the sentence can't do the deed himself, hear the last words of the victim then maybe the culprit doesn't deserve to die. Also, it makes the killings harder to do as the Lord himself would be traumatized by it where the alternative is letting a Headsman doing it and the Lord remaining unaffected by the actual deed.
Eddard Stark explained this custom and its wisdom to Bran:
"But you mistake me. The question was not why the man had to die, but
why I must do it."
Bran had no answer for that. "King Robert has a headsman," he said,
"He does," his father admitted. "As did the Targaryen kings before
him. Yet our way is the older way. The blood of the First Men still
flows in the veins of the Starks, and we hold to the belief that
the man who passes the sentence should swing the sword. If you would take a man's life, you owe it to him to look into his eyes and
hear his final words. And if you cannot bear to do that, then perhaps
the man does not deserve to die.
"One day, Bran, you will be Robb's bannerman, holding a keep of your
own for your brother and your king, and justice will fall to you. When
that day comes, you must take no pleasure in the task, but neither
must you look away. A ruler who hides behind paid executioners soon
forgets what death is."
AGOT - Bran I
Jeyne Westerling was also confused by this custom of the Northmen when Robb insisted on carrying out a spoilerish punishment himself:
"I know. I told him, he should use a headsman. When Lord Tywin
sends a man to die, all he does is give the command. It's easier
that way, don't you think?"
"Yes," said Catelyn, "but my lord husband taught his sons that
killing should never be easy."
Which Lords have the legal right to pass judicial verdicts?
This is the most interesting and important bit in your question. Who can give justice, punishments?
The King is the ultimate fountain of justice and judicial authority. As Ned explained:
"It is all the king's justice," Ned told him. "North, south, east, or
west, all we do we do in Robert's name."
However, as the King can't be expected to sit in every matter, he delegates that duty to Lords of his realm to do as they see fit in their own dominions.
"Your ladyship rode onto Standfast land, and did harm of one of Ser
Eustace's," Dunk said, before he stopped to think about it.
"Did I?" She tugged her braid again. "If you mean the sheep-stealer,
the man was notorious. I had twice complained to Osgrey, yet he did
nothing. I do not ask thrice. The king's law grants me the power of
pit and gallows."
It was Egg who answered her. "On your own lands," the boy insisted.
"The king's law gives lords the power of pit and gallows on their
Dunk and Egg: The Sworn Sword
However, only Lords can do that. Landed Knights do not have the legal right to imprison someone or execute someone.
"Clever boy," she said. "If you know that much, you will also know
that landed knights have no right to punish without their liege lord's
leave. Ser Eustace holds Standfast of Lord Rowan. Bennis broke the
king's peace when he drew blood, and must answer for it." She looked
to Dunk. "If Ser Eustace will deliver Bennis to me, I'll slit his
nose, and that will be the end of it. If I must come and take him, I
make no such promise."
Dunk and Egg: The Sworn
So in conclusion:
- King is the ultimate fountain head who may delegate the right to pass judgment to his lords, which appears to be the de-jure feudal contract of Westeros.
- Lords can do justice as they see fit on their own lands.
- Landed Knights can't do justice without permission of their liege Lords first.
Why didn't Eddard Stark send Gared back to the wall?
As Proven above, Eddard has the right and duty to perform justice in King's name on his own lands. As Lord Paramount of North, he can do that anywhere in the North, overriding the authority of the Local vassal lord just like the King can override Eddard's authority in the North.
So Eddard had to execute Gared because:
- Gared was caught on his lands.
- Punishment for deserting the Night's Watch is death.
- Eddard had the legal right and duty to kill the deserters caught in his land and send the head back to the Wall if he wants to. As it is his duty, not just right, Eddard is not the kind of man to shirk off his duties.
How did Gared get back from lands beyond the wall?
This has already been asked. See my previous answer in this regard here.