I like the matroid intersection theorem. Basically, this hammer often renders a problem trivial once you generalize to matroids. Also, it's nice that the hammer itself is not hard to prove. First the statement of the theorem.
Matroid Intersection Theorem. Let $M_1$ and $M_2$ be matroids on the same ground set $E$, with rank functions $r_1$ and $r_2$ respectively. Then the size of a maximum common independent of $M_1$ and $M_2$ is
\[ \min_{A \subset E} \ r_1(A)+r_2(E-A). \]
I won't include a proof, but you can find one in say Volume B of Combinatorial Optimization by Schrijver. It turns out that this theorem simultaneously proves many theorems such as König's theorem and Nash-Williams' theorem on covering graphs with $k$ edge-disjoint spanning trees. Here's another application.
Rainbow Spanning Trees. Let $G$ be a graph with a (not necessarily proper) $k$-colouring of $E(G)$. Suppose you are trying to decide if $G$ contains a rainbow spanning tree. That is a spanning tree such that no two edges of the tree are the same colour. One obvious necessary condition is as follows. If I choose $t$ colours and remove all the edges with these colours, then the resulting graph better have at most $t+1$ components. Is this also sufficient? This seems that it could be rather tricky to prove. However, there is an easy proof using matroids.
Let $M_2$ be the matroid whose independent sets are those subsets of edges which contain at most 1 edge of each colour. Let $M_1$ be the cycle matroid of $G$. Then, $G$ has a rainbow spanning tree if and only if $M_1$ and $M_2$ have a common independent set of size $|V(G)|-1$.
By the matroid intersection theorem it suffices that
\[ \min_{A \subset E} \ r_1(A)+r_2(E-A) \geq |V(G)|-1. \]
Note that $r_1(A)$ is simply $|V|-c(A)$, where $c(A)$ is the number of components of the subgraph $(V,A)$. On the other hand, $r_2(E-A)$ is just the number of colours among $E-A$. Rearranging yields
\[ \min_{A \subset E} \ r_2(E-A) -c(A) + 1 \geq 0, \]
which proves sufficiency.
