I just taught the Karger-Stein randomized mincut algorithm in my graduate algorithms class. This is a real algorithmic gem, so I can't not teach it, but it always leaves me frustrated, because I don't know any other applications of the main technique. (So it's hard to assign homework that drives the point home.)
Karger and Stein's algorithm is a refinement of an earlier algorithm of Karger, which iteratively contracts random edges until the graph has only two vertices; this simple algorithm runs in $O(n^2)$ time and returns a minimum cut with probability $\Omega(1/n^2)$, where $n$ is the number of vertices in the input graph. The refined "Recursive Contraction Algorithm" iteratively contracts random edges until the number of vertices drops from $n$ to $n/\sqrt{2}$, recursively calls itself twice on the remaining graph, and returns the smaller of the two resulting cuts. A straightforward implementation of the refined algorithm runs in $O(n^2\log n)$ time and returns a minimum cut with probability $\Omega(1/\log n)$. (There are more efficient implementations of these algorithms, and better randomized algorithms.)
What other randomized algorithms use similar branching amplification techniques? I'm especially interested in examples that don't (obviously) involve graph cuts.