Merging Two Binary Search Trees
In ArXiv:1002.4248, John Iacono and Özgür Özkan describe a relatively simple algorithm to merge two binary search trees in $O(\log^2 n)$ amortized time; the analysis is the hard part.  [Update: As Joe correctly observes in his answer, this algorithm is due to Brown and Tarjan.]  They also describe a more complicated dictionary data structure, based on biased skip lists, that supports merges in $O(\log n)$ amortized time. 

On the other hand, a worst-case bound of $O(\log n)$ is impossible.  Consider two binary search trees with $n$ nodes, one storing the even integers between $2$ and $2n$, the other storing the odd integers between $1$ and $2n-1$.  Merging the two trees creates a new binary search tree storing all integers between $1$ and $2n$.  In any such tree, a constant fraction of the nodes have different parity than their parents.  (Proof: The parent of an odd leaf must be even.)  Thus, merging the even and odd trees requires changing $\Omega(n)$ pointers.