Aut $\mathbb Z_p\simeq \mathbb Z_{p-1}$

What you've said so far is correct, but the fact that the group is cyclic of order $p-1$ is significantly harder. You'll need some real idea here; it's not a matter of just following your nose.

One standard approach is to prove the Cyclicity Criterion: a group $G$ of finite order $n$ is cyclic $\iff$ for each divisor $d$ of $n$ there are at most $d$ elements $x$ with $x^d = 1$ (the identity element). This is generally proved using a counting argument, and it is helpful to know that $\sum_{d \mid n} \varphi(d) = n$, where $\varphi(d) = \# (\mathbb{Z}/d\mathbb{Z})^{\times}$ is the number of integers $1 \leq e \leq d$ with $\gcd(e,d) = 1$.

With that in hand you should observe that $\mathbb{Z}/p\mathbb{Z}$ is a field, and thus the number of roots of the polynomial $x^d - 1 = 0$ in it is at most $d$. This argument ends up showing a little more: any finite subgroup of the multiplicative group of a field is cyclic.

P.S.: If I tell you that the result is often called "existence of primitive roots modulo $p$", that may help you look it up in many standard introductory texts on algebra and/or number theory.

Take an automoprhism, show it must come from multiplication by nonzero in $\mathbb{Z}_p$ by looking at what it does to 1 and by using that it is a homomorphism. Then show that this group is cyclic (primitive roots and all that jazz). This comes down to existence of primitive roots, which is where the rub is. Then you will have that the automorphism group is cyclic of $p-1$ elements, whence the answer.

Here's an another method. We need to prove that Aut $\mathbb Z_p\simeq \mathbb Z_{p-1}$ (p prime).

We know that Aut $\mathbb Z_p\simeq U(p)$

By Gauss's result, we know that when $p$ is prime, then $U(p^k) \simeq Z_{\phi(p^k)} $

Hence, $U(p) \simeq Z_{p-1} $

Since, isomorphism follows transitivity laws : $=> Aut ~ \mathbb Z_p\simeq \mathbb Z_{p-1}$ when $ p$ is prime.