How many basis functions used in STO-3G and 6-31+G** for the water molecule?
Notation


** is just a synonym for (d,p), so that 6-31+G** basis is just a different name of 6-31+G(d,p) one. 
The meaning of (d,p) is that one set of d-type polarisation functions is added for heavy atoms and one set of p-type polarisation functions is added for hydrogens.
6-31G(3pd) is essentially 6-31G(3p1d), i.e. it is 6-31G plus 3 sets of p-type polarisation functions and 1 set of f-type polarisation  functions on heavy atoms.


How many functions are there in a set?


There are always 3 functions of p-type, but the situation with d- and f-type functions is a bit more involved.
There are either 5 or 6 functions of d-type and either 7 or 10 functions of f-type depending on is a calculation restricted to use only spherical harmonics or not.


Cartesian vs. spherical harmonics

Basis functions can be written in two forms: as spherical harmonics
$$
  N(n, \alpha) Y_m^l r^n e^{-\alpha r^2}
$$
or Cartesian ones
$$
  N(l_x, l_y, l_z, \alpha) x^{l_x} y^{l_y} z^{l_z} e^{-\alpha r^2} \, .
$$
And for $l \geq 2$ the number of Cartesian harmonics is greater than spherical harmonics. For instance, a set of d-type function can have five spherical harmonics ($d_{3z^2-r^2}$, $d_{xz}$, $d_{yz}$, $d_{xy}$, $d_{x^2-y^2}$) or six Cartesian harmonics ($d_{zz}$, $d_{xx}$, $d_{yy}$, $d_{xz}$, $d_{yz}$, $d_{xy}$). Note that these six Cartesian harmonics can be transformed into five above mentioned spherical harmonics of d-type plus one function of s-type that can be neglected. Similarly, there are 10 Cartesian f-type functions and 7 spherical ones, and the later  could be constructed from the former with 3 p-type functions as a by-product.

The choice which harmonics to use can be controlled through the corresponding option in an input file and default choice varies from program to program. If you're specifically interested in Gaussian, then, if I remember correctly, by default Cartesian d-type functions and spherical f-type functions are used for the Pople 6-31G basis set. Thus, there will be 6 functions in a set of d-type functions and 7 functions in a set of f-type functions. This might be the case that Pople basis sets were even originally defined to use Cartesian d-type functions and spherical f-type ones, but I'm not sure.