In S05E02 of Game of Thrones King Stannis Baratheon offers Jon Snow lordship of Winterfell and the North and a legitimisation. First of all, can anyone legitimise a bastard except for their father? And also, can the King release a man of the Night's Watch from their vows or was Stannis just saying that his vow didn't matter because he took it before "false Gods"?
This is really two questions, so I'll answer it in two parts.
The question of legitimization, I believe, is pretty clearly answered: only a King can do so. In the novels, for example, Roose Bolton's son is legitimized by Tommen, though I don't know if that's made as clear in the show. In either case, "King" Robb legitimized Jon Snow before he died, when he thought he was King of the North, so it seems reasonable that this is how things work on the show as well.
This topic of leaving the Night's Watch is trickier. It has been discussed over at SF&F, in relation to the novels, but the same analysis applies to the TV series, as far as I know.
The short answer is: "in theory, probably not, but in practice, probably yes."
From a strictly "legal" standpoint, no one has the authority to let someone out of the vows to the Night's Watch. For starters, the Watch is effectively an autonomous organization; they specifically do not owe fealty to the King of Westeros, in order to avoid being drawn into any political bickering. Secondly, the vows that the Brothers take aren't to a person or an organization, but to their lifetime of service. They're swearing directly to their gods, so there isn't anyone with a higher authority to countermand that decision.
I'm not sure why @Mooz's answer is getting such negative attention, but he correctly points out that Martin sort-of addressed this issue in a 1999 online chat show, which would be just after A Clash of Kings was published (meaning it was likely discussing Jon Snow taking over for Robb, as opposed to any offer from Stannis).
Granny: Is there any chance that Jon could be released from his oaths of the nightwatch?
George_RR_Martin: The great council would have released Aemon from his maester's oath, so I suppose it would be possible. With an appropriate authority.
Note that Martin doesn't tell us what the "appropriate authority" is; I doubt he meant that a Great Council (who's job is to select a King) could have done it, merely that the concept of releasing someone from lifetime oaths is valid. His answer implies some other "appropriate" authority could do that for a Night's Watchman, assuming one could be found. It also implies that such an authority is not likely to be as mundane as the King of Westeros, or he probably would have just said so.
However, in practice, lack of authority wouldn't make much of a difference if the King of Westeros really wanted to get someone out. As much as the Night's Watch doesn't "let" people out of their vows, they aren't likely to argue with the entire Westerosi army over it. There's some dialog from A Storm of Swords related to this exact issue, which is just valid for the series:
[Catelyn]: “If Jon is a brother of the Night’s Watch, sworn to take no wife and hold no lands. Those who take the black serve for life.”
[Robb]:“So do the knights of the Kingsguard. That did not stop the Lannisters from stripping the white cloaks from Ser Barristan Selmy and Ser Boros Blount when they had no more use for them. If I send the Watch a hundred men in Jon’s place, I’ll wager they find some way to release him from his vows.”
Also, keep in mind that the Night's Watch relies on the Seven Kingdoms to find and punish deserters; that's a large part of what the Warden of the North does in terms of official duties. If Jon Snow "deserts" his post and newly-crowned King Stannis officially pardons him, there's almost no chance he will ever pay for his crimes.
So, if Stannis really wanted to legitimize Jon Snow and pull him out of the Night's Watch, he lacks the de jure authority to do so, but has the de facto authority to get away with it anyway.
First of all, can anyone legitimise a bastard except for their father?
Only a king may legitimize a bastard. Not even a father can do that. Lots of precedent to that. In the show canon, we have Ramsay Snow who was legitimized by King Joffrey as a reward for his father's service in the Red Wedding. Historically, King Aegon IV legitimizing his bastards lead to the civil war known as the Blackfyre Rebellion.
Can the King release a man of the Night's Watch from their vows?
Not really. A vow is a religious undertaking, and thus far only a religious institution may release one from his vows. For instance, the High Septon released King Joffrey from his promise to marry Sansa Stark in order for him to marry Margaery Tyrell. However, a king is a very powerful figure and would be able to sway the religious institutions to go his way (which is what happened in King Joffrey's case) or bestow his protection on the vow-breaker from any repercussions. So Stannis' promise was real, only Jon's personal reluctance prevented him from becoming Jon Stark.
I will add from a correspondence with George R. R. Martin:
[Interviewer] Is there any chance that Jon could be released from his oaths of the nightwatch?
[George_RR_Martin] The great council would have released Aemon from his maester's oath, so I suppose it would be possible. With an appropriate authority.
The Great Council could be convened to release someone from their vows. This has never happened before, so there is no precedent, but in theory GRRM believes it is possible.
Absolutely, he can.
While there's all sorts of questions that can be raised about the ethics and morality of it (not to mention the religious aspect of swearing the oath before their gods), legally the deserters are executed as part of the "king's justice."
This is actually one of the first things we see in season one. After being attacked by white walkers, Gared deserts and is summarily executed by Ned Stark. The books play out the same way as the show, and they are what I have in front of me.
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.
Game of thrones Chapter 1
And in case it's not clear exactly what "the king's justice" means, Ned passes an official judgement before the delivering the execution.
[Bran's] father peeled off his gloves and handed them to Jory Cassel, the captain of his household guard. 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.”
Game of thrones Chapter 1
All of this means that Stannis has the authority to pardon Jon for his "desertion," then name him lord of Winterfell.