Reading my textbook, it tells me that to prove $n$ is prime, all that is necessary is to find one of its primitive roots and verify that the order of one of these primitive roots is $n-1$.
Now, why exactly does this work? It's not making much sense to me. Also, will any primitive root work?
On
If there exists a primitive root, this already means that $(\mathbb Z/n)^{\times} \cong \mathbb Z/\varphi(n)$ is cyclic, where $\varphi$ is Euler's totient function. If $\varphi(n) = n-1$, then $n$ is prime.
On
If you verify the order of $a$ is $n-1$, then $a$ is a primitive root. This means that $a^k \equiv 1\mod n\; \forall \;1\le k \le n-1$, and it is true that $a^k$ takes on all values of $\{1,\dots,n-1\}$, which by Fermat's Little Theorem, means $n$ is prime.
On
Over the complex numbers, $e^{2 \pi i / n}$ is always a primitive root of unity. Presumably, you mean a root of unity that has order $n - 1$ in the multiplicative group $\Bbb{Z}_n^{\times}$.
The ring $\Bbb{Z}_n$ is an integral domain if and only if $n$ is prime since otherwise the factors of $n$ are zero divisors. Every finite integral domain is a field and the multiplicative group of a finite field is cyclic. Therefore, if $n$ is prime, $\Bbb{Z}_n$ has a root of unity of order $n - 1$. On the other hand, if $n$ is not prime then $\Bbb{Z}_n^{\times}$ contains an element $b$ that is not invertible and so no power of a root $a$ of unity can be equal to $b$. It follows that the order of $a$ is less than $n - 1$.
Yes, any primitive root will work.
Effectively what we have established, by raising the primitive root $m$ to the power $(n-1)$ and that being the lowest power for which we encounter $1 \pmod n$, is that there are $(n-1)$ distinct numbers less than $n$ that don't divide $n$. If there were some $k<n-1$ which had $\gcd(m^k, n) = c \ne 1$, we could never get rid of the factor of $c$ and so we would not reach $m^{n-1} \equiv 1 \bmod n$.
To find a primitive root is perhaps more of a challenge. For a number $n$ that we don't know is prime, we need to check that our candidate root $m$ fulfills $m^{n-1} \equiv 1 \bmod n$ (failure on this count would immediately mean that $n$ is not prime) and then check that it also fulfills $m^{k} \not\equiv 1 \bmod n$ for each $k = \frac{n-1}{p_i}$ where $p_i$ are the distinct prime factors of $(n-1)$.