At first I thought a solution wouldn't be too hard to find: simply take the triangle graph and attach various subgraphs to each node. This doesn't work, because it either: doesn't restrict any symmetries, or restricts too many symmetries.
It's apparently not as easy as it sounds to construct graphs with cyclic automorphism groups, but a little googling returned this Mathworld page. Just find the word "cyclic" on the page to see some examples.
There is definitely a concept of an automorphism group of a set. It's just the permutation group of that set (the set of all functions from that set to itself, under the operation of function composition).
The following may or may not be helpful:
Most objects we study in math form these things called categories. The definition of a category is pretty simple, but very abstract. Essentially, a category is a collection of objects and "maps" between these objects called morphsims.
For example, the category of groups has groups as objects and homomorphisms as morphisms. The category of sets has sets as objects and functions as morphisms.
Morphisms which have two-sided inverses are called isomoprhisms. An isomorphism between an object and itself is called an automorphism. For example, in the category of groups, the only morphisms which have two-sided inverses are the bijective ones, and so automorphisms are bijective homomorphisms from a group to itself.
A very important property of morphisms is that some morphisms can be composed together (and this composition is associative).
Given any category $\mathcal C$ and an object $X$ in $\mathcal C$, we can for the automorphism group of $X$, denoted $\mathrm{Aut}(X)$, which is the set of all automorphisms of $X$ under composition.
Groups, graphs, and sets all form categories, so each of these objects has an automorphism group. The automorphism group $\mathrm{Aut}(X)$ really is a group, even if the object $X$ is not a group (as we've seen, it could be a set or a graph).
Best Answer
Fun facts: (i) The $(i,j)$th entry of any matrix $M$ is equal to $e_i^TMe_j$, where $e_i$ is the vector with $1$ in the $i$th entry and $0$ elsewhere. (ii) $e_{\pi(i)} = Pe_i$, where $P$ is the matrix corresponding to the permutation $\pi$. (iii) Every permutation matrix $P$ is orthogonal, i.e. $P^T = P^{-1}$.
Let the adjacency matrices of the original and permuted graphs be $A$ and $B$. We want the $(\pi(i),\pi(j))$th entry of $B$ to be the same as the $(i,j)$th entry of $A$ is $1$. Equivalently, we want $(Pe_i)^TB(Pe_j) = e_i^TAe_j$. For this to hold for all $i$ and $j$, we must have $P^TBP = A$, or $B = PAP^T$.
If the permutation preserves adjacency, then $A = B = PAP^T$, so $AP = PAP^TP = PA$. Therefore $P$ commutes with $A$.