The way I view Yoneda's lemma as a generalization of Cayley's theorem is by viewing a group as a category with one object $o$. To see how a category with one element is a group, let the points of the group be morphisms $f:o\rightarrow o$. By the definition of a category, we must have an identity morphism $id_o:o\rightarrow o$, and this is the identity of the group. Similarly, morphisms are associative, so $f\circ (g\circ h) = (f\circ g)\circ h$. So composition is the group operation. As for invertibility, let's just force our morphisms to be invertible by assuming they are all isomorphisms. Ok, so now the collection of morphisms forms a group in the sense we learn in undergrad.
Cayley's Theorem says we can embed a group $G$ into $Sym(G)$, the set of bijections $f:G\rightarrow G$. This means we have an isomorphism $G\cong H$ for some $H\leq Sym(G)$. If we're going to generalize this to category theory we need to understand maps that take morphisms to morphisms (those are our group elements, after all). Functors do this, so a generalization of Cayley's Theorem needs to say something about embedding a category $\mathcal{C}$ into a category of functors going out of $\mathcal{C}$. If I want a category of functors, I need to know what maps are between functors. They are natural transformations.
Now, Yoneda's Lemma says we have $\mathrm{Nat}(h^A,F) \cong F(A)$ where $h^A = Hom(A, − )$ and $F$ is any functor from $\mathcal{C}$ to the category of Sets. If we set $F$ to be the forgetful functor then we have $F(A)\cong A$, $f:A\rightarrow A$ going to $Ff:A\rightarrow A$, and $f\circ g: A\rightarrow A$ going to $Ff\circ Fg: A\rightarrow A$. This means the group structure is preserved, so we're viewing the group $\mathcal{C}$ as $F(A)$ and it sits in a category of functors as $\mathrm{Nat}(h^A,F)$.