What is the best way to see that the dimension of the moduli space of curves of genus $g>1$ is $3g-3$? This fact was apparently known to Riemann. How did Riemann think about this?

At that time, it was not known that there existed a variety of moduli of smooth curves, so his count was really a moduli count, in the latin sense. I think the strategy in Riemann's count was to count covers of the projective line by all smooth curves at a time, in two ways.
First way. Fix a smooth curve $C$. Let us study degree $d$ covers $C\to\mathbb P^1$. To give one of these is the same as to give two linearly independent sections of some $L\in \textrm{Pic}^d(C)$. Now, fix one such $L$, and assume $d$ is big enough (say $d>2g-2$). Then $h^0(L)=d-g+1$. This means that, having fixed $C$ and $L$, there is a $2(d-g+1)-1=2d-2g+1$dimensional family of degree covers $C\to\mathbb P^1$ attached to $L$. (The $-1$ is just to identify $(s,t)$ with $(as,at)$, for $a\in\mathbb C^\times$). Now, $\textrm{Pic}^d(C)\cong \textrm{Pic}^0(C)$ has dimension $g$. So, let us vary the line bundle $L$ and the curve to get the count we want: we get $$(2d-2g+1)+g+\dim M_g=2d-g+1+\dim M_g.$$
Second way. Using (the currently named) Riemann-Hurwitz formula. Any cover has then $2g+2d-2$ branch points and thanks to Riemann's Existence Theorem, which classifies covers of the projective line, we know that no correction term is needed, so that $$2d-g+1+\dim M_g=2g+2d-2,$$ whence $\dim M_g=3g-3$.
You may want to look up to E. Looijenga lecture notes, where he explains this in another, yet similar fashion in the section "Riemann moduli count".
By the way, since the title of your question starts with "what is the best way", I cannot help doing this remark: from deformation theory, the Zariski tangent space of $M_g$ at a point $[C]$ is isomorphic to $$H^1(C,\mathcal T_C),$$ which in turn - by Serre duality - is isomorphic to $$H^0(C,\omega_C^{\otimes 2})^\prime,$$ and by Riemann-Roch the latter has dimension $$h^0(C,\omega_C^{\otimes 2})=2(2g-2)+1-g=3g-3,$$ having observed that $\deg \omega_C^{\otimes 2}>2g-2$.
