One of the most interesting, and complicated, features of general relativity is the fact it is a non-linear theory, i.e., adding solutions together won't yield a solution.
One example of that behavior is a Schwarzschild black hole, which means a black hole with no charge and no rotation (a spinning black hole is a bit more complicated, but it would work as well). The Schwarzschild solution is what is known as a vacuum solution: there is no matter in the spacetime. At any point in spacetime you look, there won't be matter. Still, there certainly is gravity.
One of the pictorial ways of interpreting this is by noticing that the gravitational field itself possesses "energy" (in quotation marks, because the notion of energy in general relativity is complicated, as mentioned in this blog post by Sean Carroll). By means of $E=mc^2$, having energy means, in some sense, having mass, and hence the gravitational field is a source of even more gravitational field. The gravitational energy "creates" more gravity, which leads to more gravitational energy, and then more gravity and... And this is essentially what we call non-linearity. The effects start piling up on each other and the description gets quite complicated. Far more complicated than what one has in Newtonian gravity or Maxwellian electromagnetism, both of which are linear theories.
Notice then that if you add two solutions together, you'll be increasing the amount of gravitational energy. That is a source of more gravity, and hence you'll need to account for this extra gravity, which was not present in the two original solutions.
Disclaimer: notice that this "energy creates more gravity" view is pictorial, and meant only to bring more intuition. There is no way of assigning an "adequate" notion of energy to the gravitational field (see the Sean Carroll blog post for some more detail). While this picture can be used as a way of getting intuition and interpretation, it does have limitations and should be taken with a grain of salt.
Black Holes are made of Vacuum
I noticed this bit of the answer caused some discomfort on the comments, so maybe I should add some more resources on it. I believe Kip Thorne is someone particularly famous who quite often mentions how black holes are made of warped spacetime, instead of compact matter. His comments appear in this site now and again. Here are some instances:
I should also have added before that all of my answer should be understood in the context of General Relativity, which means I'm neglecting all quantum effects. Within the framework of General Relativity, spacetime is a differentiable Lorentzian manifold, which means it must have a well-behaved metric at all points. This prevents the singularity of Schwarzschild spacetime from being a point in the manifold, since a curvature scalar blows up "there". Hence, in the description provided by General Relativity, there is not a single point in Schwarzschild spacetime where there is matter. All points are at vacuum.
"But near the singularity, quantum gravity effects should kick in and—" I agree. This description is not necessarily final, and most likely it will be modified by quantum effects. However, it is important to distinguish what happens in the actual Universe—in which the Schwarzschild solution doesn't even exist, since we had a Big Bang and we have a positive cosmological constant—and what is described by General Relativity. I discussed similar issues (the difference between theory and reality) in this post about Classical Electrodynamics. It is one thing to ask whether an actual black hole corresponds to complete vacuum, and another thing to ask whether a GR solution is a vacuum solution.