As you said, we know that $|G:Z(G)|=|G:C_G(x)|\cdot|C_G(x):Z(G)|$ for any $x\in G$.
Let's suppose that $|G:Z(G)|$ is prime. This means that $G$ is non-abelian. So we can take an element $x\in G\setminus Z(G)$. Using the above formula, we know that either
since $p$ is prime.
We cannot be in the first state of affairs because $|G:C_G(x)|=1$ implies that $x$ is in the center contrary to our choice that $x\in G\setminus Z(G)$.
In addition, we cannot be in the second state of affairs because $|C_G(x):Z(G)|=1$ implies that $C_G(x)=Z(G)$. The contradiction arises from the fact that $x$ commutes with itself; and since the elements that commute with $x$ are precisely the elements of the center, we have that $x\in Z(G)$. This is the same contradiction as before.
I'm going to elucidate the $G/Z(G)$ argument, since it's much more general and I believe it's important for you to understand. Let $Z=Z(G)$ to save on space.
Suppose $G$ is a group such that $G/Z$ is cyclic. Let $aZ$ be a generator for $G/Z$ for some $a\in G$ (recall all elements of $G/Z$ are cosets of $Z$). Since $Z$ is normal, we have that for all $a,b\in G$ that $aZ\cdot bZ=(ab)Z$ (this is the property that allows us to give a natural binary operation on $G/Z$).
In particular, this means that all elements of $G/Z$ are of the form $a^nZ$ for some $n\in\Bbb Z$. Now let $x, y\in G$. The projection map takes these elements to $xZ$ and $yZ$ respectively. From what we just learned, we know that $xZ=a^nZ$ and $yZ=a^mZ$ for some $n$ and $m\in\Bbb Z$. This means that $x$ and $a^n$ lie in the same coset of $Z$; the same applies to $y$ and $a^m$.
This in turn implies that there is an $h_1$ and an $h_2\in Z$ such that $x=a^nh_1$ and $y=a^mh_2$.
Now we just compute:
Since $x$ and $y$ were arbitrary, $G$ is abelian.