A stag's a male animal, a hen's a female animal - that's the only reason really, no other connection. I guess there might be a problem keeping the species the same and calling a stag night a c*ck night...
And why hen? Well have you ever heard a bunch of clucking women on a hen night...?
'Stag' was originally used in the USA as a noun in the early 1900s to refer to a man unaccompanied by a lady. Thereafter, it began to be used as an adjective, as in 'stag party' etc. 'Hen' has been used to refer to women since as far back as the 1600s. 'Hen party', however, did not appear anywhere before the 1960s.
possibly another case of double standards - the men go out and behave like rutting stags, girls, booze etc and women were expected to stay at home on a hen night and cluck about the dress and cake etc