Gared's crime was against the Night's Watch.
Should he not have been returned to them, so that they could do justice as they saw fit?
Do all lords of the kingdom have ongoing permission to execute deserters from the Watch?
Also, How did Gared ever slip through Castle Black without being recognized and journey hundreds of kilometres to Winterfell, alone, with no horse and no supplies?
When someone joins the Night's Watch, he takes some vows:
Night gathers, and now my watch begins. It shall not end until my death. I shall take no wife, hold no lands, father no children. I shall wear no crowns and win no glory. I shall live and die at my post. I am the sword in the darkness. I am the watcher on the walls. I am the fire that burns against the cold, the light that brings the dawn, the horn that wakes the sleepers, the shield that guards the realms of men. I pledge my life and honor to the Night's Watch, for this night and all the nights to come
-- A Game of Thrones, Chapter 48, Jon.
Which are some vows for life. People are allowed to leave before they finish their training and take their vows, but not afterwards. Their vows are for life. The deserters are sentenced to death.
So, it would be pointless for Eddard to sent him back to the Wall, since he was going to be executed there as well. That's why he wanted to execute him where he found him. It would be a long trip in the snows for not a really good reason.
I cannot say for sure that any lord can do this, but Eddard was in good relations with the Night's Watch, since all the Starks have helped the Wall through the ages. Even if this was a crime, it would be forgiven.
In addition to Shevliaskovic's answer, Ned may have thought it too risky to bring the man back to the Night's Watch. As he explains to Bran in Chapter 1 of AGOT:
"In truth, the man was an oathbreaker, a deserter from the Night’s Watch. No man is more dangerous. The deserter knows his life is forfeit if he is taken, so he will not flinch from any crime, no matter how vile."
Tradition and Honour
The reason why it was Ned who executed the man was because he was personally carrying out the King's Justice, as pointed out in the following passages from A Game of Thrones:
But the man they found bound hand and foot to the holdfast wall awaiting the king’s justice
Ned takes his role as the Lord of Winterfell very seriously
He had taken off Father’s face, Bran thought, and donned the face of Lord Stark of Winterfell.
Ned explains his sentencing:
He took hold of Ice with both hands and said, “In the name of Robert of the House Baratheon, the First of his Name, King of the Andals and the Rhoynar and the First Men, Lord of the Seven Kingdoms and Protector of the Realm, by the word of Eddard of the House Stark, Lord of Winterfell and Warden of the North, I do sentence you to die.” He lifted the greatsword high above his head.
And Ned explains to Bran why it had to be him:
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, uncertainly.
“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.
The lords of the 7 Kingdoms have not just permission, but an obligation to execute deserters from the Night's Watch. That is as close to a law of the land as we can get in Westeros. This quote
"In truth, the man was an oathbreaker, a deserter from the Night’s Watch. No man is more dangerous. The deserter knows his life is forfeit if he is taken, so he will not flinch from any crime, no matter how vile."
does not just mean that it is risky or impractical to bring the deserter back to the Night's Watch, but that that the deserter knows that he will be killed if caught anywhere south of the Wall.
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:
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, uncertainly.
"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."
ASOS- Catelyn III
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."
AGOT- Eddard XI
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 own lands."
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 Sword
So in conclusion:
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:
This has already been asked. See my previous answer in this regard here.
