I have the following Cayley graph: $$ ...\cdot \leftrightarrow \cdot \leftrightsquigarrow \cdot \leftrightarrow \cdot \leftrightsquigarrow \cdot \leftrightarrow ...$$
Here are my thoughts: we have two generators $a,b$. And $a^2=b^2=e$ since we have arrows going out and back from $e$ to $a$ and $b$. So this group is the group of words $ababa...aba$ which can start and end with either $a$ or $b$. Is it the same as a free group with two relations: $\langle a, b\ |\ a^2, b^2\rangle$? Is my interpretation correct?
Yes, your interpretation is correct. There are no further relations since there are no loops in the Cayley graph except those deducible from the relations $a^2 = b^2 = e$.
The group $\langle a, b \mid a^2, b^2 \rangle$ is known as the infinite dihedral group.