The reason why that inequality is equivalent to RH (for curves) is the functional equation.
The polynomial $L(z)$ I speak about below would arise in practice as the numerator of the zeta-function of the curve, with $z = q^{-s}$ and the usual version of the Riemann hypothesis for $L(q^{-s})$ is equivalent to the statement that the reciprocal roots of $L(z)$ all have absolute value $\sqrt{q}$. That's the form of the Riemann hypothesis I will be referring to in what follows.
Suppose we have a polynomial $L(z)$ over the complex numbers with constant term 1 and degree $d$, factored over its reciprocal roots:
$$
L(z) = (1 - \alpha_1z)\cdots(1-\alpha_dz), \ \ \ \alpha_j \not= 0.
$$
Let $L^*(z)$ be the polynomial with complex-conjugate coefficients to those of $L(z)$, so
$$
L^*(z) = (1 - \overline{\alpha_1}z)\cdots(1-\overline{\alpha_d}z).
$$
Assume $L(z)$ and $L^*(z)$ are connected by the functional equation
$$
L(1/qz) = \frac{W}{z^d}L^*(z)
$$
for some constant $W$. If you compare coefficients of the same powers of $z$ on both sides, this functional equation implies the mapping $\alpha \mapsto q/\overline{\alpha}$ sends reciprocal roots of $L(z)$ to reciprocal roots of $L^*(z)$ (and $W$ has absolute value $q^{d/2}$).
Lemma 1. Granting the functional equation above, the following conditions are equivalent:
i$)$ the reciprocal roots of $L(z)$ have absolute value $\sqrt{q}$ (RH for $L(z)$),
ii$)$ the reciprocal roots of $L(z)$ have absolute value $\leq \sqrt{q}$.
Proof. We only need to show ii implies i.
Assuming ii, let $\alpha$ be any reciprocal root of $L(z)$,
so $|\alpha| \leq \sqrt{q}$. By the functional
equation, $q/\overline{\alpha}$ is a reciprocal
root of $L^*(z)$, so $q/\overline{\alpha} = \overline{\beta}$
for some reciprocal root $\beta$ of $L(z)$.
Then $|q/\overline{\alpha}| = |\overline{\beta}| = |\beta| \leq \sqrt{q}$ and thus $\sqrt{q} \leq |\alpha|$.
Therefore $|\alpha| = \sqrt{q}$ and i follows. QED
This lemma reduces the proof of the Riemann hypothesis for $L(z)$ from the equality $|\alpha_j| = \sqrt{q}$ for all $j$ to the upper bound $|\alpha_j| \leq \sqrt{q}$ for all $j$. Of course the functional equation was crucial in explaining why the superficially weaker inequality implies the equality.
Next we want to show the upper bound on the $|\alpha_j|$'s in part ii of Lemma 1 is equivalent to a $O$-estimate on sums of powers of the $\alpha_j$'s which superficially seems weaker.
We will be interested in the sums
$$
\alpha_1^n + \cdots + \alpha_d^n,
$$
which arise from the theory of zeta-functions as coefficients in an exponential generating function: since $L(z)$ has constant term 1, we can write (as formal power series over the complex numbers) $$L(z) = \exp\left(\sum_{n \geq 1}N_n z^n/n\right)$$
and then logarithmic differentiation shows
$$
N_n = -(\alpha_1^n + \dots + \alpha_d^n)
$$
for all $n \geq 1$.
Lemma 2.
For nonzero complex numbers $\alpha_1,\dots,\alpha_d$ and a
constant $B > 0$, the following are equivalent:
i$)$
For some $A > 0$, $|\alpha_1^n + \dots + \alpha_d^n| \leq AB^n$ for
all $n \geq 1$.
ii$)$
For some $A > 0$ and positive integer $m$,
$|\alpha_1^n + \dots + \alpha_d^n| \leq AB^n$ for
all $n \geq 1$ with $n \equiv 0 \bmod m$.
iii$)$ $|\alpha_j| \leq B$ for all $j$.
Part ii is saying you only need to show part i when $n$ runs through the (positive) multiples of any particular positive integer to know it is true for all positive integers $n$. It is a convenient technicality in the proof of the Riemann hypothesis for curves, but the heart of things is the connection between parts i and iii. (We'd be interested in part iii with $B = \sqrt{q}$.) You could set $m = 1$ to make the proof below that ii implies iii into a proof that i implies iii. The passage from i to iii is what Dave is referring to in his answer when he cites the book by Iwaniec and Kowalski.
Proof.
Easily i implies ii and (since $|\alpha_j| = |\overline{\alpha_j}|$)
iii implies i.
To show ii implies iii, we use a cute analytic trick. Assuming ii, the series
$$
\sum_{n \equiv 0 \bmod m} (\alpha_1^n + \dots + \alpha_d^n)z^n
$$
is absolutely convergent for $|z| < 1/B$, so the series defines a holomorphic function on this disc. (The sum is over positive multiples of $m$, of course.)
When $|z| < 1/|\alpha_j|$ for
all $j$, the series can be computed to be
$$
\sum_{j=1}^{d} \frac{\alpha_j^mz^m}{1-\alpha_j^mz^m} =
\sum_{j=1}^{d}\frac{1}{1-\alpha_j^mz^m} - d,
$$
so the rational function $\sum_{j=1}^{d} 1/(1-\alpha_j^mz^m)$ is holomorphic
on the disc $|z| < 1/B$. Therefore the poles of this rational function must have absolute value $\geq 1/B$. Each $1/\alpha_j$ is a pole, so $|\alpha_j| \leq B$ for all $j$. QED
Theorem.
The following are equivalent:
i$)$ $L(z)$ satisfies the Riemann hypothesis ($|\alpha_j| = \sqrt{q}$ for all $j$),
ii$)$ $N_n = O(q^{n/2})$ as $n \rightarrow \infty$,
iii$)$ for some $m \geq 1$, $N_n = O(q^{n/2})$ as $n \rightarrow
\infty$ through the multiples of $m$.
Proof.
Easily i implies ii and ii implies iii.
Assuming iii, we get $|\alpha_j| \leq \sqrt{q}$ for all $j$ by
Lemma 2, and this inequality over all $j$ is equivalent to i
by Lemma 1. QED
Brandon asked, after Rebecca's answer, if the inequality implies the Weil conjectures (for curves) and Dave also referred in his answer to the Weil conjectures following from the inequality. In this context at least, you should not say "Weil conjectures" when you mean "Riemann hypothesis" since we used the functional equation in the argument and that is itself part of the Weil conjectures. The inequality does not imply the Weil conjectures, but only the Riemann hypothesis (after the functional equation is established).
That the inequality is logically equivalent to RH, and not just a consequence of it, has some mathematical interest since this is one of the routes to a proof of the Weil conjectures for curves.
P.S. Brandon, if you have other questions about the Weil conjectures for curves, ask your thesis advisor if you could look at his senior thesis. You'll find the above arguments in there, along with applications to coding theory. :)
Consider the two following potential definitions of stability of a locally free coherent sheaf $E$.
(A) Every subbundle (i.e. locally free subsheaf) has strictly smaller slope.
(B) Every subsheaf has strictly smaller slope.
I claim that over a curve $X$ these two definitions are equivalent. Indeed, suppose (A) holds, and let $F\subset E$ be a subsheaf. Consider the sequence
$$0\to F\to E \to Q\to 0.$$
Here $Q$ may fail to be locally free; Put $G = Q/Q_{tors}$, which is then locally free since $X$ is a curve. Define $K$ by the sequence
$$0\to K \to E \to G\to 0,$$
and observe that $K$ is locally free of the same rank as $F$. Furthermore, $c_1(K) \geq c_1(F)$ since $c_1(Q_{tors})\geq 0$, so $\mu(F) \leq \mu(E)$.
Thus it is equivalent to only consider subbundles for stability, so long as we are working on a curve. Together with GAGA, this shows the two approaches (and any possible combination of definitions) are essentially the same.
Best Answer
Here are the statements from Schmidt's book (as pointed to in my comment).
(a) Suppose $f(x,y)$ is a polynomial of total degree $d$, with coefficients in the field of $q$ elements and with $N$ zeros with coordinates in that field. Suppose $f(x,y)$ is absolutely irreducible, that is, irreducible not only over the field of $q$ elements, but also over every algebraic extension thereof. Then $$|N-q|\le2g\sqrt q+c_1(d)$$ where $g$ is the genus of the curve $f(x,y)=0$.
I am not up to explaining "genus" without algebraic geometry, but it is known that $g\le(d-1)(d-2)/2$, so if you are willing to settle for $$|N-q|\le(d-1)(d-2)\sqrt q+c_1(d)$$ then I think you have what you are after.
(b) Let $\chi$ be a multiplicative character of order $d>1$. Suppose that $f(x)$, a polynomial in one variable over the field of $q$ elements, has $m$ distinct zeros, and is not a $d$th power. Then $$\Bigl|\sum_{x\in{\bf F}_q}\chi(f(x))\Bigr|\le(m-1)\sqrt q$$