Riemann combines what is called Riemann-Roch and Riemann-Hurwitz nowadays.
He considers the dimension of the space of holomorphic maps of degree $d$ from the Riemann surface of genus $g$ to the sphere. He computes this dimension in two ways. By Riemann-Roch this dimension is
$2d-g+1$, for a fixed Riemann surface. (Indeed, Riemann-Roch says that
the dimension of the space of such functions with $d$ poles fixed
is $d-g+1$ (when $d\geq 2g-1$ which we may assume), but these poles can be moved, so one has to add $d$ parameters).
On the other hand, such a function has $2(d+g-1)$ critical points by Riemann-Hurwitz.
Generically, the critical values are distinct, and can be arbitrarily assigned, and this gives the dimension of the set of all such maps on all Riemann surfaces
of genus $g$.
So the space of all Riemann surfaces of genus $g$ must be of dimension
$$2(d+g-1)-(2d-g+1)=3g-3.$$
Riemann-Roch is proved in section 5 of Part I and and the dimension of the moduli space is counted in section 12 of Part I of the paper cited in F. Zaldivar's answer.
Remark. Indeed, Riemann did not know about sheaves, cohomology and Serre duality. Neither he knew the general definition of a Riemann surface (which is due to Weyl). But one should take into account that all these notions were developed for the purpose to explain and digest what Riemann wrote in this paper. (Compare this with the anecdote about Hilbert, who once asked a seminar speaker: "What is the Hilbert space?").
Remark 2. A pair $(S,f)$, where $S$ is a Riemann surface, and $f$ a meromorphic function from $S$ to the Riemann sphere is called "a Riemann surface spread over the sphere'' (Uberlagerungsflache). All such pairs can be constructed in the
following way: choose critical values of $f$ and make some cuts between them
so that the remaining region on the sphere is simply connected. Then take $d$ copies of this region (they are called sheets) stack them over the sphere, and paste them together along the cuts. You obtain a surface $S$ together with a map $f$, the "vertical" projection onto the sphere. Parameters are critical values.
Riemann did not have any exact definition of "Riemann surface", he just explained this procedure of gluing as a visualization tool. For him, $S$ is a "class of algebraic curves $F(x,y)=0$ under birational equivalence". Until the work of Weyl, these pairs
$(S,f)$ were called Riemann surfaces, and only Weyl defined exactly what $S$ is. Nowadays $S$ is called a Riemann surface, and a pair $(S,f)$ a "Riemann
surface spread over the sphere".