Let me describe, in words, the method of folds due to Stallings. Pictures would be better, but perhaps you can figure out the pictures from my words.
I'll carry out the construction using your example $H = \langle a^3,ab^3\rangle$, which as it turns out has infinite index, not index 9. (You may have been deceived by the fact that the abelianization of $H$ has index $9$ in the abelianization of $F_{a,b}$)
Let $R$ be a graph with one vertex and two oriented edges labelled $a,b$, representing the free group $F_{a,b}$.
To represent $H = \langle a^3, ab^3 \rangle$, draw a graph $G$ with one vertex and two oriented edges $A,B$. Subdivide $A$ into three oriented edgelets labelled $a,a,a$. Subdivide $B$ into four oriented edgelets labelled $a,b,b,b$. These labellings define a simplicial map $f : G \to R$ taking each $a$ edgelet of $G$ to the $a$-edge of $R$, and similarly for $b$. Notice that $H$ equals the image of the induced map of $f$:
$$H = \text{Image}\bigl(\pi_1(G) \xrightarrow{f_*} \pi_1(R) = F_{a,b}\bigr)
$$
You might notice: $f : G \to R$ is not locally injective (details below).
The strategy is: simply $G$ and the map $G \xrightarrow{f} R$ until one has a locally injective map.
The simplification step is: "Stallings folds".
In order to explain the first Stallings fold, I'll first explain the non-local-injectivity of $f:G \to R$. At the valence 4 vertex $v \in G$ there are four directions with initial vertex $v$: the initial ends of two $a$-edgelets which I will call "$a$-directions"; the terminal end of one $a$-edgelet which I will call a "$\bar a$-direction"; and the terminal end of one $b$-edgelet which I will call a "$\bar b$-direction". The reason that $f:G \to R$ is not locally injective is because of the two $a$-directions at $v$.
Now we're ready to do the first Stallings fold. Define a quotient map $f_1 : G \to G_1$ by folding: take the two $a$-edgelets of $H_0$ whose initial $a$-directions are located at $v$, and identify those two $a$-edgelets to a single $a$-edgelet of $G_1$. The graph $G_1$ inherits a subdivision into oriented and labelled edgelets from the graph $G$.
By the way that $G_1$ and $f_1$ were constructed, it follows that the map $G \xrightarrow{f} R$ factors as
$$G \xrightarrow{f_1} G_1 \xrightarrow{g} R
$$
Notice three things:
- $G_1$ is homeomorphic to a $\theta$ graph, with two vertices of valence 3.
- The map $g : G_1 \to R$ is locally injective. From this, it follows pretty easily that the induced $\pi_1$ map $g_* : \pi_1(G_1) \to \pi_1(R) = F_{a,b}$ is injective.
- The maps $f$ and $g$ have the same $\pi_1$-induced image, which equals $H$.
The map $g : G_1 \to R$ is locally injective and so it shares an important property with covering maps, but it is not a covering map. To correct this, examine each vertex of $G_1$, examine the directions at that vertex, and attach a tree of $a,b$-edges to recover the covering map property.
For instance, $G_1$ has a valence $3$ vertex $w$ with an $a$-direction, a $\bar a$-direction, and a $\bar b$-direction, but it is missing a $b$-direction which accounts for why the covering map property fails at $w$. To correct for this, attach to $w$ a copy of a subtree of the Cayley graph of $F_{a,b}$, namely the subtree which contains the identity vertex of the Cayley graph, and the $b$-direction at the identity vertex, and every embedded path in the Cayley graph that starts with that $b$-direction.
After you have done similar appropriate tree attachements to each vertex of $G_1$, you obtain a covering map to $R$ which represents the subgroup $H$. This covering map has infinite degree, hence $H$ has infinite index.
The general method will usually require more than just one fold, but if you understand this one example you'll probably understand the method in general.
Best Answer
Hint: Instead of thinking about index 3 subgroups of $\Bbb Z \star \Bbb Z$, consider what connected 3-fold covers of $S_1 \vee S_1$ look like. Any such cover is a connected graph on 3 vertices of valence 4 (why?), and there are only finitely many such graphs. Then use deck transformations to check if each cover is regular.