Whenever $G$ is finite and its automorphismus is cyclic we can already conclude that $G$ is cyclic.
Because as we already saw $G$ is abelian and finite, we can use the fundamental theorem of finitely generated abelian groups and say that wlog
$G=\mathbb{Z}/p^k\mathbb{Z} \times \mathbb{Z}/p^j \mathbb{Z}$. But the automorphismgroup isn't abelian and hence isn't cyclic.
For non finite groups the implication isn't true.
The following is from this link and only slightly reworded.
Let $G$ be the subgroup of the additive group of rational numbers comprising those rational numbers that, when written in reduced form, have denominators that are square-free numbers, i.e., there is no prime number $p$ for which $p^2$ divides the denominator.
Then:
The only non-identity automorphism of is the negation map, so the automorphism group is $\mathbb{Z}/2\mathbb{Z}$, and is hence cyclic.
The group $G$ is not a cyclic group. In fact, it is not even a finitely generated group because any finite subset of can only cover finitely many primes in their denominators. It is, however, a locally cyclic group: any finitely generated subgroup is cyclic.
To prove equivalence of the definitions, we do the following:
$(1)$ If $G=\{g^k:k\in\Bbb Z\}$ then we need to show it is isomorphic to $\Bbb Z/n\Bbb Z$ for some $n$ or $\Bbb Z$. This can be done by showing $g^k\mapsto k$ is an isomorphism (if $|G|<\infty$ then we map to $\Bbb Z/|G|\Bbb Z$).
$(2)$ If $G$ is isomorphic to $\Bbb Z/n\Bbb Z$ for some $n$ or $\Bbb Z$, we need to show it can be written as $\{g^k:k\in\Bbb Z\}$. Under this isomorphism, you map the identity in $\Bbb Z$ or $\Bbb Z/n\Bbb Z$ to some $g\in G$ then show that $G=\{g^k:k\in\Bbb Z\}$. Take an arbitrary $x\in G$, then $x=\phi(k)$ for some $k$ where $\phi$ is the isomorphism with range $G$. Then, $\phi(k)=\phi(1)^k=g^k$.
Best Answer
This answer is almost complete and I think (read hope) that it's correct up to the point where I get stuck. (I've posted this as an answer because it's too long for a comment and I should go to bed.)
It suffices by the first isomorphism theorem to find a group $H$ and a surjective homomorphism $\theta : G \to H \times H$ for which $\ker \theta = Z(G)$.
By spelling out the definitions it is easy to see that $G/Z(G)$ is commutative if and only if $g^{-1}h^{-1}gh \in Z(G)$ for all $g,h \in G$, which occurs if and only if $[G,G] \le Z(G)$, where $[G,G]$ is the commutator subgroup of $G$.
This implies that the map $G \to [G,G]$ defined by $x \mapsto g^{-1}x^{-1}gx$ is a homomorphism for fixed $g \in G$, since if $y \in G$ then $$\begin{align} (g^{-1}x^{-1}gx)(g^{-1}y^{-1}gy) &= g^{-1}(x^{-1}gxg^{-1})y^{-1}gy \\ &= g^{-1}y^{-1}(x^{-1}gxg^{-1})gy \\ &= g^{-1}y^{-1}x^{-1}gxy \\ &= g^{-1}(xy)^{-1}g(xy) \end{align}$$ Likewise the map $x \mapsto x^{-1}h^{-1}xh$ is a homomorphism for fixed $h \in G$.
Since $Z(G)$ is cyclic, so is $[G,G]$, and hence it is generated by a single element $g^{-1}h^{-1}gh$ for some $g,h \in G$.
Fix $g,h \in G$ such that $[G,G] = \langle g^{-1}h^{-1}gh \rangle$. Let $H = [G,G]$ and define $\theta : G \to [G,G] \times [G,G]$ by $$\theta(x) = (g^{-1}x^{-1}gx, x^{-1}h^{-1}xh)$$ Now