How does git bisect skip choose the next commit to try?

I did some digging into the Git source code and found most of an answer myself...

As of Git v1.6.4 (specifically, as of commit ebc9529f), Git uses "a PRNG (pseudo random number generator) with a bias" to determine which commit to try next after skipping one.

I can't say I follow the algorithm itself (which, as of v2.8.1, appears to be fundamentally untouched since it was first added), but the commit message does a reasonable job of explaining what's going on:

bisect: use a PRNG with a bias when skipping away from untestable commits

Using a PRNG (pseudo random number generator) with a bias should be better than alternating between 3 fixed ratios.

In repositories with many untestable commits it should prevent alternating between areas where many commits are untestable. The bias should favor commits that can give more information, so that the bisection process should not loose much efficiency.

HPA suggested to use a PRNG and found that the best bias is to raise a ratio between 0 and 1 given by the PRNG to the power 1.5.

So it looks as though Git picks the next commit to try at random, but the random distribution was picked to (hopefully) choose commits that give more information for the binary search and to avoid commits likely to be in regions of untestable commits.