I've come across the picture you're looking for in physics textbooks before (say, in classical mechanics). A bit of googling and I found this one for you!
Alternatively, we can use the first fundamental form to determine the surface area element. Recall that this is the metric tensor, whose components are obtained by taking the inner product of two tangent vectors on your space, i.e. $g_{i j}= X_i \cdot X_j$ for tangent vectors $X_i, X_j$. We make the following identification for the components of the metric tensor,
$$
(g_{i j}) = \left(\begin{array}{cc}
E & F \\
F & G \end{array} \right),
$$
so that $E = <X_u, X_u>, F=<X_u,X_v>,$ and $G=<X_v,X_v>.$
We can then make use of Lagrange's Identity, which tells us that the squared area of a parallelogram in space is equal to the sum of the squares of its projections onto the Cartesian plane: $$|X_u \times X_v|^2 = |X_u|^2 |X_v|^2 - (X_u \cdot X_v)^2.$$
Here's a picture in the case of the sphere:

This means that our area element is given by
$$
dA = | X_u \times X_v | du dv = \sqrt{|X_u|^2 |X_v|^2 - (X_u \cdot X_v)^2} du dv = \sqrt{EG - F^2} du dv.
$$
So let's finish your sphere example. We'll find our tangent vectors via the usual parametrization which you gave, namely,
$X(\phi,\theta) = (r \cos(\phi)\sin(\theta),r \sin(\phi)\sin(\theta),r \cos(\theta)),$
so that our tangent vectors are simply
$$
X_{\phi} = (-r\sin(\phi)\sin(\theta),r\cos(\phi)\sin(\theta),0), \\
X_{\theta} = (r\cos(\phi)\cos(\theta),r\sin(\phi)\cos(\theta),-r\sin(\theta))
$$
Computing the elements of the first fundamental form, we find that
$$
E = r^2 \sin^2(\theta), \hspace{3mm} F=0, \hspace{3mm} G= r^2.
$$
Thus, we have
$$
dA = \sqrt{r^4 \sin^2(\theta)}d\theta d\phi = r^2\sin(\theta) d\theta d\phi
$$