  We present efficient algorithms for counting points on a smooth plane quartic
curve $X$ modulo a prime $p$. We address both the case where $X$ is defined
over $\mathbb F_p$ and the case where $X$ is defined over $\mathbb Q$ and $p$
is a prime of good reduction. We consider two approaches for computing
$\#X(\mathbb F_p)$, one which runs in $O(p\log p\log\log p)$ time using $O(\log
p)$ space and one which runs in $O(p^{1/2}\log^2\!p)$ time using $O(p^{1/2}\log
p)$ space. Both approaches yield algorithms that are faster in practice than
existing methods. We also present average polynomial-time algorithms for
$X/\mathbb Q$ that compute $\#X(\mathbb F_p)$ for good primes $p\le N$ in
$O(N\log^3\! N)$ time using $O(N)$ space. These are the first practical
implementations of average polynomial-time algorithms for curves that are not
cyclic covers of $\mathbb P^1$, which in combination with previous results
addresses all curves of genus $g\le 3$. Our algorithms also compute
Cartier-Manin/Hasse-Witt matrices that may be of independent interest.
