How do I prove that $x^p-x+a$ is irreducible in a field with $p$ elements when $a\neq 0$?

$x \to x^p$ is an automorphism sending $r$ to $r-a$ for any root $r$ of the polynomial. This operation is cyclic of order $p$, so that one can get from any root to any other by applying the automorphism several times. The Galois group thus acts transitively on the roots, which is equivalent to irreducibility.

Greg Martin and zyx have given you IMHO very good answers, but they rely on a few basic facts from Galois theory and/or group actions. Here is a more elementary but also a longer approach.

Because we are in a field with $p$ elements, we know that $p$ is the characteristic of our field. Hence, the polynomial $g(x)=x^p-x$ has the property $$g(x_1+x_2)=g(x_1)+g(x_2)$$ whenever $x_1$ and $x_2$ are two elements of an extension field of $\mathbb{F}_p$. By little Fermat we know that $g(k)=k^p-k=0$ for all $k\in \Bbb{F}_p$. Therefore, if $r$ is one of the roots of $f(x)=x^p-x+a$, then $$f(r+k)=g(r+k)+a=g(r)+g(k)+a=f(r)+g(k)=0,$$ so all the elements $r+k$ with $k \in \Bbb{F}_p$ are roots of $f(x)$, and as there are $p$ of them, they must be all the roots. It sounds like you have already shown that $r$ cannot be an element of $\Bbb{F}_p$.

Now assume that $f(x)=f_1(x)f_2(x)$, where both factors $f_1(x),f_2(x)\in \Bbb{F}_p[x]$. From the above consideration we can deduce that $$ f_1(x)=\prod_{k\in S}(x-(r+k)), $$ where $S$ is some subset of the field $\Bbb{F}_p$. Write $\ell=|S|=\deg f_1(x)$. Expanding the product we see that $$ f_1(x)=x^\ell-x^{\ell-1}\sum_{k\in S}(r+k)+\text{lower degree terms}. $$ This polynomial was assumed to have coefficients in the field $\Bbb{F}_p$. From the above expansion we read that the coefficient of degree $\ell-1$ is $|S|\cdot r+\sum_{k\in S}k$. This is an element of $\Bbb{F}_p$, if and only if the term $|S|\cdot r\in\Bbb{F}_p$. Because $r\notin \Bbb{F}_p$, this can only happen if $|S|\cdot1_{\Bbb{F}_p}=0_{\Bbb{F}_p}$. In other words $f_1(x)$ must be either of degree zero or of degree $p$.

$f(x)$ is separable since its derivative is $f'(x) = -1 \ne 0$.

Suppose $\theta$ is a root of $f(x) = x^p - x + a$. Using the Frobenius automorphism, we have: \begin{align} f(\theta + 1) &= (\theta + 1)^p - (\theta + 1) + a\\ &= \theta^p + 1^p - \theta - 1 + a\\ &= \theta^p - \theta + a\\ &= f(\theta) = 0 \end{align}

Thus, by induction, if $\theta$ is a root of $f(x)$, then $\theta + j$ is also a root for all $j \in \mathbb F_p$.

By above, if $f(x)$ were to have a root in $\mathbb F_p$, then $0$ would a be a root too, but this contradicts $a \ne 0$. Thus, $f(x)$ has no roots in $\mathbb F_p$. (This can also be shown using Fermat's little theorem.)

Suppose $\theta$ is a root of $f(x)$ in some extension of $\mathbb F_p$. We know that $\theta + j$ is also a root for all $j \in \mathbb F_p$. Since $f(x)$ is of degree $p$, these are all of the roots of $f(x)$.

Clearly, $\mathbb F_p(\theta) = \mathbb F_p(\theta + j)$ for all $j \in \mathbb F_p$. Thus, all $\{\theta + j\}$ have the same degree over $\mathbb F_p$. Since $f(x)$ is separable, it follows that $f(x)$ must be the product of all minimal polynomials of $\{\theta + j\}$. Suppose the minimal polynomials have degree $m$. We have $p = km$ for some $k$. Since $p$ is prime, either $m = 1$; hence $\theta \in \mathbb F_p$, a contradiction. Or $k = 1$; hence $f(x)$ is irreducible because it's the minimal polynomial.