MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 added 1146 characters in body; deleted 9 characters in body; deleted 10 characters in body

I'm late to the party, but here's how I think about this fact. The approach I will present is perhaps slightly higher-tech higher tech than some, but has the advantage that it's a completely general way of computing a free finite-index subgroup of a virtually free group.

It's also easy to see that these subgroups are the minimal-index torsion-free subgroups: any covering of $G$ by a genuine graph $\widehat{G}$ must have even degree, so that the vertices above $u$ have trivial label; and it must have degree dividing divisible by three, so that the vertices above $v$ have trivial label.

Exactly the same argument can be made to work for $SL_2(\mathbb{Z})$, which you of course should think of as $\mathbb{Z}/4*_{\mathbb{Z}/2}\mathbb{Z}/6$. Indeed, if I have it right, these techniques should prove the following theorem, which is presumably standard, although I don't know a reference. (Warning: I haven't thought about this very hard.)

Note that this technique is powerful enough to let you compute all the conjugacy classes of all the subgroups of a given index, if you want. (Update: though there are some subtleties if you really want to do this; see below.)

(At the moment what I'm seeing doesn't quite square with some of the other answers/comments: I get one normal free subgroup of $PSL_2(\mathbb{Z})$ of index six, and one conjugacy class of non-normal free subgroups of index six, corresponding to a regular covering of $G$ and an irregular covering, respectively; this seems at odds with Mark's remark about different maps to $\mathbb{Z}/12$. \mathbb{Z}/12$. But it's late, so I'm not going to figure out what's going on now.)

Update

I had forgotten an important subtlety. A covering map of graphs of groups $\widehat{G}\to G$ includes an extra piece of information, viz:

For each vertex $\hat{v}$ of $\widehat{G}$ with image $v$ in $G$, and for each edge $e$ incident at $v$, a covering map specifies a bijection between the set of edges of $\widehat{G}$ incident at $\hat{v}$ that map to $e$ and the set of double cosets

$\widehat{G}_{\hat{v}}\backslash G_v/G_e$

(where $G_v$ is the group labelling $v$, etc). As such bijections always exist, this doesn't arise if you want to prove the existence of a subgroup. But the correct notion of equivalence for covering maps takes these bijections into account, so two different covering maps $\widehat{G}\to G$ may have the same underlying graph-map. This happens for the commutator subgroup and the Sanov subgroup: in both cases, the underlying graph is the first subdivision of the theta graph.
show/hide this revision's text 1

I'm late to the party, but here's how I think about this fact. The approach I will present is perhaps slightly higher-tech than some, but has the advantage that it's a completely general way of computing a free finite-index subgroup of a virtually free group.

To keep things simple, I'll do $PSL_2(\mathbb{Z})$, and then explain how to do $SL_2(\mathbb{Z})$ at the end.

As you presumably know, $\Gamma=PSL_2(\mathbb{Z})\cong \mathbb{Z}/2*\mathbb{Z}/3$. You should think of it as the fundamental group of a graph of groups $G$, with one edge and two vertices, one of which, $u$, is labelled by $\mathbb{Z}/2$ and one, $v$, labelled by $\mathbb{Z}/3$.

Just as in the case of ordinary topology, any (conjugacy class of a) subgroup $H\subseteq\Gamma$ corresponds to a covering map $\widehat{G}\to G$. (This is a trivial consequence of Bass--Serre theory: take $\widehat{G}=T/H$ where $T$ is the Bass--Serre tree.) Coverings of graphs of groups are just like coverings of graphs, except that sometimes a neighbourhood looks like a quotient by a non-free action of a group, in which case you have to remember point stabilisers (cf. orbifolds). The subgroup $H$ is free if and only if every vertex of $\widehat{G}$ is labelled by the trivial group, in which case we can think of $\widehat{G}$ as a genuine graph and $H$ as its fundamental group.

To prove that $PSL_2(\mathbb{Z})$ has a free subgroup of index $6$, we now just have to construct a covering map $\widehat{G}\to G$ of degree $6$, where $\widehat{G}$ is a genuine graph. But this is easy. To do this, take three vertices $u_1,u_2,u_3$ of valence two and two vertices $v_1,v_2$ of valence three. Now glue them together however you like, such that each edge adjoins one $u_i$ and one $v_j$. (I think there are exactly two ways of doing this, up to permuting the $i$'s and $j$'s.) The covering map $\widehat{G}\to G$ sends $u_i\mapsto u$ and $v_j\mapsto v$, and each edge goes to the unique edge of $G$. Whichever way you do the gluing, the graph $\widehat{G}$ has rank two, so the subgroup is isomorphic to $F_2$.

It's also easy to see that these subgroups are the minimal-index torsion-free subgroups: any covering of $G$ by a genuine graph $\widehat{G}$ must have even degree, so that the vertices above $u$ have trivial label; and it must have degree dividing three, so that the vertices above $v$ have trivial label.

Exactly the same argument can be made to work for $SL_2(\mathbb{Z})$, which you of course should think of as $\mathbb{Z}/4*_{\mathbb{Z}/2}\mathbb{Z}/6$. Indeed, if I have it right, these techniques should prove the following theorem. (Warning: I haven't thought about this very hard.)

Theorem: If $\Gamma=A*_CB$ for $A,B$ finite, then a minimal-index free subgroup is of index $d=\mathrm{lcm}(|A|,|B|)$, and of rank

$1-d\left(\frac{1}{|A|}+\frac{1}{|B|}-\frac{1}{|C|}\right)$.

Note that this technique is powerful enough to let you compute all the conjugacy classes of all the subgroups of a given index, if you want.

(At the moment what I'm seeing doesn't quite square with some of the other answers/comments: I get one normal free subgroup of $PSL_2(\mathbb{Z})$ of index six, and one conjugacy class of non-normal free subgroups of index six, corresponding to a regular covering of $G$ and an irregular covering, respectively; this seems at odds with Mark's remark about different maps to $\mathbb{Z}/12$. But it's late, so I'm not going to figure out what's going on now.)