See J. G. Wendell, "A problem in geometric probability", Math. Scand. 11 (1962) 109-111. The probability that $N$ random points lie in some hemisphere of the unit sphere in $n$-space is
$$p_{n,N} = 2^{-N+1} \sum_{k=0}^{n-1} {N-1 \choose k}$$
and in particular you want
$$p_{3,4} = 2^{-3} \sum_{k=0}^2 {3 \choose k} = {7 \over 8}$$.
A second solution: A solution from The Annals of Mathematics, 2 (1886) 133-143 (available from jstor), specific to the (3,4) case, is as follows. First take three points at random, A, B, C; they are all in the same hemisphere and form a spherical triangle. Find the antipodal points to those three, A', B', C'. Now either the fourth point is in the same hemisphere as the first three or it is in the triangle A'B'C'. The average area of this triangle is one-eighth the surface of the sphere.
This gets the right answer, but I'm not sure how I feel about it; why is the average area one-eighth the surface of the sphere? One can guess this from the fact that three great circles divide a sphere into eight spherical triangles, but that's hardly a proof. Generally this solution seems to assume more facility with spherical geometry than is common nowadays.
Here's an "irreversible chess" construction that's fundamentally different from the ones so far based on Ed Dean's scheme. The essential pieces and pawns are in boldface:
Position A: White Kh1, Ra1, Nd1, pawns b2,b3,c3,d2,e3,f2,g2,h7, Bg8; Black Kh8, Bb1, Bg1, pawns f7,g7,h2.
(source: janko.at)
Position D = Position A after 1...Ba2 2 Rc1 Bb1, i.e. with the Rook on c1 and White to move:
(source: janko.at)
I call it D rather than B because the two intermediate positions can be called B and C, and then each arrow in A $\rightarrow$ B $\rightarrow$ C $\rightarrow$ D is irreversible. [This was also possible in some of the previous examples, including Ed's original one; I don't think we've seen "A $\rightarrow$ B $\rightarrow$ C $\rightarrow$ D $\rightarrow$ E" yet.]
In Position A, the rook and a1 and bishop on b1 can reversibly roam the board. But after 1...Ba2 (Position B) the only locally reversible continuation is 2 Rc1 (Position C; if 2 Rb1 Black has no reversible reply) 2...Bb1 (Position D) 3 Rc2 Ba2 4 Rc1 Bb1 and we're back to D; the White rook and Black bishop can no longer escape the corner because they keep getting in each other's way.
The previous constructions all exploit the special behavior of kings, which must not be in check on the opponents' move. This new approach does not need kings at all — it would still work if we removed the kings and their un-boldfaced retinues, except that the problem as posed required each side to have a king. The key ingredient here instead of the check rule is move alternation: if either side were allowed to skip a turn it would be easy to get back to Position A — whereas in several of the check-based constructions, skipping turns would not help as long as neither side is allowed to make a move (even as part of an unanswered series) that leaves its own king in check.
Best Answer
James correctly identified percolation theory as the place where something like this is studied seriously. But let's do an elementary calculation.
Each possible path consists of $4n-1$ squares and is uniquely specified by saying which $2n-1$ of the $4n-2$ squares other than the first is vertically above the square before. Thus, there are exactly $$\binom{4n-2}{2n-1}$$ possible paths. Each path appears in a random board with probability $2^{-4n+1}$. Therefore, the expected number of paths is $$2^{-4n+1}\binom{4n-2}{2n-1} \sim \frac{1}{\sqrt{8\pi n}},$$ where the last expression comes from Stirling's formula.
Since the expected number of paths goes to 0, the probability that there is at least one path goes to 0 at least as fast. A quick simulation shows that James is correct that the probability goes to 0 exponentially fast (maybe slightly faster than $2^{-n}$).