I know how the English governmental and electoral system works, but there’s one question I wondered about repeatedly when readinga bout Britsih politics: What if a party wins the majority in the House, but the leader of the party loses his own constituency and therefore does not become MP? I guess the parties mostly nominate their leaders for strongholds, making sure this does not happen, but suppose Blair had lost Sedgefield, but Labour still wins the election as a whole. Would he be appointed Prime Minister nonetheless, or would the party nominate someone else for PM?
If Mr Blair had lost his seat but the Labour Party had still won a majority in the House of Commons, then the remaining members of the Labour Party would get together and elect a new party leader. The Queen would then commission the new leader of the Labour Party as PM.
Not necessarily. Its just as likely that a Labour MP in a safe seat who did win would resign so that the Party Leader could then stand in that seat and be returned to parliament.
In 1963, there was a not disimilar occurence. Harold McMillan resigned as Prime Minister for health reasons. His chosen successor* was Lord Alex Douglas-Home, who was a member of the House of Lords. Even back in 1963, it was considered an anachronism to have a Prime Minister from the Upper House, so Douglas-Home resigned his peerage (using the same act that Tony Benn used). A junior conservtive MP then resigned his seat and Sir Alex won the re-election at Kinross & West Perthshire.
*This, in itself, in a whole other story.
Also, don’t forget that the Prime Minister doesn’t have to be the party leader - the government is formed by whoever the Queen invites to form it.
Its only convention that dictates that this is the Leader of the largest party in parliament.
This process is referred to as kissing hands
Prime Ministers don’t fight unwinnable constituencies. If boundary changes start to make the seat look doubtful they do the chicken run for a new one (as Gordon Brown had to this time)
And isn’t it too a convention that the leader of said party must be a MP?
What would prevent the Labour from keeping Blair as leader, had he not been relected?
Can anyone in the UK run for any constituency? Are there no requirements to actually reside in the area?
No , but what usually happens is that when someone is chosen to stand for that constituency they usually move into the area , even though this might mean just actually living there for a couple of days a week.
They could keep him on, but constitutional convention would dictate that he had to get a seat in the Commons quickly, as others have pointed out.
There’s no hard-and-fast rule for how a party deals with this issue - really, it depends upon whether the PM still has the support of the party. If he’s got that support, they’d be willing to let someone else resign in a safe seat to get him back into Parliament. But if the PM’s support is shaky to start with, failure to win his own seat could be enough to rally opposition to him within the party and lead to a leadership challenge.
In a Canadian example, Prime Minister King’s government won re-election in 1925, but King lost his seat. There were apparently some rumblings of a leadership challenge, but King managed to fight it off long enough to win a safe seat. If his opponents within the party had been stronger, it’s possible he could have been booted from the leadership position and replaced by someone else.
It’s the same in Canada - no residency requirment. Heck, you don’t even have to live in the province where your riding is located. In the King example, King had held a seat in Ontario. After he lost it in the 1925 election, the MP for Prince Albert, Saskatchewan, resigned and King ran there. He never moved to Saskatchewan, but represtented Prince Albert for the next 20 years, until the voters of that riding defeated him. Undeterred, he had an MP in North York, Toronto, resign, and successfully ran there.
On a side note the Prime Minister’s constituency can throw up some interesting candidates. This year’s highlights were (party name in brackets):
Cherri Blairout-Gilham (Pensioners Party)
William John Brown (We Want Our Country Back)
Jonathan McQueen Cockburn (The Blair Must Go Party)
Melodie Elizabeth Staniforth (The Official Monster Raving Loony Party)
Elections just wouldn’t be the same without the Monster Raving Loony Party to liven things up 
Huh? Doesn’t his new enlarged constituency include most of his old one?
(And not only do you not have to live in a constituency to run for it, you can also stand in more than one…)
The Monster Raving Loonies have not been the same since Lord Sutch died. They need a new leader. Perhaps they could choose Kilroy-Silk , he’s mad as a hatter.
Yup, otherwise parties like Veritas, UKIP and the Greens couldn’t exist. Of course, to be Prime Minister you need to be an MP though (and preferably have some experience as a Government Minister) - so they need to get elected at some point! 
POP QUIZ! Only two Prime Ministers this Century have been elected who’ve had no prior Ministerial experience. Who were they?
Or rather in the Twentieth Century :wally
Ramsey MacDonald and Tony Blair?
It’s a nitpick, but Kinross & West Perthshire was actually going to have a by-election anyway and so it only required that the Conservative candidate stand aside, rather than have an MP resign. And, incidentally, that candidate was George Younger, who went on to have a significant ministerial career in the 80s.
Mr. MacDonald and Mr Blair were elected PMs in the last century. (Unless “this century” refers to the 1900s 
)
So is it correct to say that the answer to the OP’s question is –
If Blair had lost his seat in his constituency election, things would be put on hold until another safe-Labour seat came open (perhaps by the resignation of a sitting Labour M.P.) and Blair won that seat in a bye-election. Blair would then be elected party leader by the Labour members of the House of Commons and his name would be presented to the queen in the usual way.
Is that it?