Gary Martin at The Phrase Finder has the British phrase third time lucky derived from the earlier "proverbial" luck of the third adventure, traced in print back to 1839. As to the reason for the luck, the theory of it referring to an English law freeing a condemned man after three failed attempts at hanging is debunked. He concludes:
It seems more likely that it is just a folk belief that, having had setbacks, we ought to persevere and not give up. This is enshrined in the phrase 'try, try and try again'. Three seems to be the right number of times to try. Two isn't enough but four is too many. Think of every time you've seen a drama in which a character tries to unlock a door with an set of unfamiliar keys. The first key fails, the second key fails - it is always the third that works.
And on its relatonship to the American version, third time's the charm:
This may be an variant of the earlier 'third time lucky' or it may have arisen independently in the USA.
A citation is given of this phrase from 1912.
EDIT:
Please don't vote this answer up. A few minutes with Google turned much of it on its head. See my other answer (pending).