Why aren't all black holes the same "size"? The center of a black hole is a singularity.  By definition, a singularity has infinite density.  So how can a black hole with a different mass or density be described?
 A: Far away from a black hole, spacetime is curved only a little bit, and many different things could curve it like that out there.
It's like if you had a dollar in your pocket, and it's been there for a long time, and you can't remember if you got it from your boss or from your friend.  But a dollar is a dollar.
So you could have a massive star, or a black hole, but from far away, it's hard to tell which it is, but you know the curvature is what it is.  You could notice that it is the kind of curvature that makes you go in a circle at a certain speed, with a certain circumference.  Since you are far away and the curvature is small, everything approximates Newtonian physics quite well.
So a mass of M would generate an acceleration due to gravity of $GM/r^2$, which for a circular motion gives $v^2/r=GM/r^2$, so $v^2r/G=M$.  Now you can relate the circumference to $2\pi r$, so if $C$ is the circumference, you get $M=v^2r/G=v^2C/2\pi G$.  And if $v$ is hard to measure (since motion is relative) you can relate your speed $v$ to the period $T$ by $vT=C$.
Thus $M=v^2C/2\pi G=v^2T^2C/2\pi GT^2=C^3/2\pi GT^2$.
So, since the period $T$ can be measured (by a stopwatch) far from the body, and the circumference can be measured (by a meter stick) far from the body, we can get this relationship entirely from measurements done far from the body where there are weak fields and everything is well approximated by Newtonian Physics.  So from far away we can tell how massive something is by doing measurements from far away.  These measurements don't depend on how dense something is, just how massive it is.  So we can tell how massive something is from measurements from far away.  And it is that massive because it curves space and time exactly like something that massive would curve it.
You only notice that something is a black hole when you get really really close to it.  When you try to get close to something that isn't very dense you bump into before the gravitational effects are very strong.  Since a black hole is very dense, it just means you can get closer to it (and feel stronger effects close to it) without bumping into it.  But everywhere you can tell how massive it is.
And the mass is not, emphatically not, the sum of the masses of the parts.  The energy of the interaction of the parts matters, the pressure matters, the stress matters, lots of things contribute to how strong a gravitational effect is.
A: It's almost certainly incorrect that the center of a black hole is a singularity as this would be at odds with quantum mechanics. Just how exactly it looks like would be something to ask of a theory of quantum gravity!
Regardless of being a singularity or not, the mass is determined by how much mass you stuff into your black hole. Hence black holes of arbitrary total mass can exist, until Hawking radiation brings it back to zero mass.
A: The singularity probably does not exist, as GR likely breaks down at those size / energy scales. When we have a full quantum description of gravity we may know what's really there.
By the way, the part of the black hole we fully understand is actually the vacuum solution - the Schwarzschild metric - which includes the event horizon but not the source mass. GR is agnostic about what happens on the inside and only cares about the total energy content.
A: Although we don't have a quantum theory of gravity, we think we have some reliable knowledge about the properties of black holes from general relativity. 
One thing we think we know is the so-called "No-hair conjecture", which says that black holes can be described by just three numbers: mass, charge, and angular momentum (i.e. how much they are spinning).
Black holes with different mass differ by the size of their event horizon (the point of no return); for a common black hole solution in general relativity (Schwarzschild black hole), the relationship is linear:
$$
R \propto M
$$
So that's the answer to your question: even if black holes of all masses all contain a singularity, heavier black holes have bigger event horizons.
A: The density of black holes isn't infinite. Some black holes have the billionfold density of our sun (like the black holes in center of galaxies). There are big and small black holes.
A: What matters is the mass of the black hole. All black holes have a singularity that has no size, no space or time. These break down and become meaningless at the singularity. Since space is meaningless, so is density. It only has mass. The amount of matter that has fallen into the black hole determines its mass. The more mass/matter a singularity has the larger its event horizon. So, the greater the black hole's mass the larger it is.
