Is there a word for a Cayley graph for knots? Given a group $G=\langle S\vert R\rangle$, the Cayley graph $\Gamma(S,R)$ assigns each element of $G$ to a vertex of $\Gamma$, assigns each generator $s\in S$ to a color, and assigns an $s$-colored vertex connecting $g$ to $gs$ for $g\in G$ and $s\in S$.  Many interesting questions about the group $G$ can be asked/answered by investigating $\Gamma$.
Given a knot diagram of a knot $K$, Reidemeister's theorem shows that the Reidemeister moves generate all knots equivalent to $K$.  We can form a graph $\Psi$ considering each planar isotopy of $K$ as a vertex, each of the three Reidemeister moves $\{R_1, R_2, R_3\}$ as generators, and, for all isotopies $k_i$ equivalent to $K$, an $R_j$ colored vertex connecting $k_1$ to $k_2$ if there's an $R_j$ move that converts $k_1$ to $k_2$.

Is there a name for such a "Cayley graph" on knots?

 A: I have not heard of a name for such a graph, but the combinatorial structure is described implicitly when considering the following two part problem.

Suppose we are given a diagram $D$ of the unknot.

*

*Is there a bound on the number of Reidemeister moves necessary to transform $D$ into the standard diagram of the unknot, say in terms of the crossing number of $D$?


*Is there an unknot diagram $D$ such that every sequence of Reidemeister moves taking $D$ to the unknot must increase the number of crossings of $D$?

Both of these questions can be interpreted as questions on the "Reidemeister graph" you describe. The first is asking if there is a bound on the length of the shortest path between a vertex in the Reidemeister graph of the unknot and the special vertex in that graph representing the crossing-less diagram of the unknot. The second question involves "weighting" each vertex with the crossing number of the corresponding diagram, and then asking if there is a path between a given vertex and the crossing-less unknot vertex such that the weights on the path never increase.
Both of these questions have been answered in the affirmative. For question 1, Hass and Lagarius proved that a diagram of the unknot with $c(D)$ crossings can be unknotted in at most $2^{10^{11}c(D)}$ Reidemeister moves. This bound has been improved on significantly by Lackenby, Henrich and Kauffman, and probably others.
The answer to the second question is also yes. Goeritz (paywall warning, sorry) found the first such example in 1934. Kauffman and Lambropoulou gave a way to produce infinitely many such knots (called hard unknots).
As you note in the comments above, one can consider not just knot diagrams and Reidemeister moves, but also other representations of knots and the sets of moves between those representations. I will mention two related results.
Every knot can be represented by a grid diagram. The analogue of Reidemeister moves in this setting are the Cromwell moves. Dynnikov proved that given a grid diagram of the unknot on an $n\times n$ grid, there is a sequence of Cromwell moves that results in the smallest diagram of the unknot such that size of the grid either remains the same or decreases at each step.
In a similar fashion, Schultens defined the width complex for a knot. Roughly the vertices of the width complex are knot diagrams and the edges have to do with isotopies that can change the width of the diagram. Zupan proved that there are "local minima" (corresponding to the hard unknots above) in the width complex.
Although I have not given you an exact answer, the essence of your combinatorial structure is at the heart of many questions in knot theory. As a final thought, the work of Gordon and Luecke and Waldhausen implies that the triple $(\pi, m, \ell)$ determines that knot (where $\pi$ the fundamental group of the complement of a knot, $m$ is a meridian of the knot, and $\ell$ is a longitude of the knot). One could similarly look at the Cayley graph of $\pi$ with the two generators $m$ and $\ell$ somehow being "special" and hope to extract information about the knot.
A: I’m adding a new answer because just today a relevant paper hit the arxiv. Barbensi and Celoria just posted a paper about Reidemeister graphs of knot diagrams. They consider two such graphs, one for knot diagrams in $\Bbb{R}^2$ and one for diagrams in $S^2$. 
Their main result is that the isomorphism type of the $S^2$ Reidemeister graph determines the knot up to mirror images. They prove this result holds if we restrict to certain finite subgraphs of the Reidemeister graph. 
They explore lots of local properties of the Reidemeister graph as well. I think this is just the type of paper you were looking for. 
