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. :)
Best Answer
(1) We have $$ N_n(X) = \sum_{k = 0}^{2d} (-1)^k \mathrm{tr}\left(\mathrm{Frob}^n \colon H^k(X) \to H^k(X) \right) = \sum_{k = 0}^{2d} (-1)^k \sum_{i=1}^{ h^k(X)} \lambda_{k,i}^n$$
where $\lambda_{k,1},\dots,\lambda_{k,h^k(X)}$ are the eigenvalues of $\mathrm{Frob}$ on $H^k(X)$, counted with multiplicity.
Furthermore, we have $|\lambda_{k,i}| =q^{k/2}$ so $\left| \lambda_{k,i}^n\right| = q^{nk/2}$ as long as $X$ is a smooth projective variety (or even smooth proper). (If $X$ is not proper, we need to use compactly-supported cohomology to obtain the formula for the number of points, and then we only obtain an upper bound for the size of the eigenvalue.)
Technically speaking, the correct statement (see Lemma 1.7 of La Conjecture de Weil I by Pierre Deligne) is that the eigenvalues are algebraic numbers all whose Galois conjugates in $\mathbb C$ have size $q^{k/2}$. This deals with the issue that the eigenvalues are naturally $\ell$-adic integers and thus aren't naturally complex numbers, by considering the complex numbers that are Galois conjugates in the sense of satisfying the same minimal polynomial.
This notational difficulty is removed if we avoid étale cohomology and merely state the Riemann hypothesis in the form that
$$ N_n(X) = \sum_{k = 0}^{2d} (-1)^k \sum_{i=1}^{ h^k(X)} \alpha_{k,i}^n$$ where $\alpha_{k,i}$ are complex numbers of absolute value $q^{k/2}$ and $h^i(X)$ is the $i$th Betti number of the de Rham cohomology of a characteristic $0$ lift.
This form is actually totally equivalent to the original formulation of Weil. We recover Weil's statement, in terms of the zeta function, by multiplying both sides by $U^n$, dividing by $n$, summing over $n$, and exponentiating. (In fact, this is exactly how Weil proves his conjecture for Fermat hypersurfaces in the paper where he originally formulates it, Number of Solutions fo Equations in Finite Fields.) We can recover this statement from Weil's by taking the logarithm of both sides, extracting the coefficient of $U^n$, and multiplying by $n$.
Of course, Weil could not give the statement in terms of étale cohomology because it hadn't been invented yet!
(2) This works in at least one notion of motives.
I think this is easiest to do if we use homological equivalence ($\ell$-adic, crystalline, whichever) as our equivalence relation for motives.
The idea here is that motives are supposed to have, for each cohomology theory, a realization functor that sends the motive to its cohomology groups, which on varieties $X$ recovers the cohomology groups of $X$, and is compatible with direct sums.
So if we express $X$ as a sum of (indecomposable, to avoid worrying about semisimplicity) motives, we can write the (signed) trace of $\mathrm{Frob}^n$ on the cohomology of $X$ as the sum of the (signed) trace of $\mathrm{Frob}^n$ on the cohomology of the motives.
To make the contribution of each motive of size $q^{kn/2}$, we just need each indecomposable motive to have cohomology only in a particular degree.
If we define motives using correspondences up to homological equivalence, say for $\ell$-adic homology, then the $\ell$-adic realization functor exists by construction.
Furthermore, because the eigenvalues of Frobenius on each cohomology group are distinct, we can define by linear algebra a polynomial in Frobenius, with rational coefficients, which acts by $1$ on the $k$th cohomology group and $0$ on each other cohomology group (the Künneth type standard conjecture). If we work with cycles up to homological equivalence, this cycle is idempotent, so defines a splitting of the motive of $X$.
Using these splittings, we can split $X$ into motives each of which has cohomology only in a single degree, as desired.
For Chow motives with respect to which other equivalence relations this can be made to work, as well as for which other notions of motives, I will leave to experts.