How many basis functions used in STO-3G and 6-31+G** for the water molecule? I am a little confused about how to decide how many basis functions that are used in a particular basis set for a given molecule.

STO-3G is a so-called "minimal basis set", meaning that only one basis function is used for each atomic orbital in the atoms of which the molecule is made from. 

The water molecule has two H atoms and one O atom, with 1s1 and 1s2 2s2 2p6 electron configurations, respectively. When STO-3G is used, would that then mean that three 1s type basis functions, one 2s type basis function, and 3 p-type basis functions are used, totalling at 7 basis functions that are used, each being made up from a linear combination (LC) of three simple Gaussian functions?

The 6-31+G** is a split-valence basis set, which includes both diffuse and polarisation functions. The two asterisks tell that polarization functions are used for both the H atom and the O atom, p and d polarization functions respectively. I am not sure "how many" polarization functions are used per atom - just 1, or one for each of the p-orbitals? (Some basis sets are of the form 6-31G(3pd); does that mean that 3 p and 1 d polarization functions are used, or 9 p functions?) The single "+" sign means that just one diffuse function is used for the O atom.
So, I think that the 6-31+G** for the water molecule equates to a total of 16 basis functions:


1s in oxygen: one LC of 6 GTOs
2s in oxygen: one LC of 3 GTOs + 1 GTO
2p in oxygen: one LC of 3 GTOs + 1 GTO (for each of px, py, and pz)
1s in hydrogen 1: one LC of 3 GTOs + 1 GTO
1s in hydrogen 2: one LC of 3 GTOs + 1 GTO
Diffuse: one diffuse basis function for the oxygen atom
Polarization: one polarised basis function for the oxygen atom
Polarization: one polarised basis function for the hydrogen atom
Total: 16


Is this correct? I do not feel confident carrying out this analysis, especially the point concerning how many polarization functions for the p/d-orbitals that should be used.
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.