Back to black holes, and this is where things get really weird. It involves quantum mechanics, which is something that Einstein never really got into. In fact, Einstein had a lot of trouble believing in quantum mechanics because it involves a lot of probability, and Einstein didn't believe that the universe could have some randomness thrown in.
Quantum mechanics came about because as we probed into the world of the ultra-small, we discovered some really new and different things that couldn't be explained by General or Special Relativity. It was discovered that every particle that makes up basic matter has a matching anti-particle. An electron (which has a negative charge) has a buddy called a positron (which has, you guessed it, a positive charge). When these two particles collide, they destroy each other and turn into energy.
Remember that old story about how matter cannot be created or destroyed? Total bs. Kind of. Matter is created and destroyed all the time, but the sum of energy and matter is always constant. Matter can't be created unless energy is used, and energy can't be created unless some matter is used. It turns out that at really small scales (called the Planck length, like 1.6 * 10^-35 meters), energy and matter are trading places constantly.
Some energy is borrowed and two particles will appear, like a quark and an anti-quark. Typically, they immediately get attracted back together, are destroyed and release the energy back to the cosmos. Now imagine this happens right at the event horizon of a black hole, but one of the particles is formed inside the event horizon and the other is outside. These particles move at the speed of light, so the one outside can escape (only things inside the event horizon can never escape) while the other one gets sucked into the black hole.
Now it may seem like this would increase the size of a black hole, but it doesn't. Space wants its energy back to be in balance. Where does it get it from? The black hole. When the two particles were formed, they took two units of energy (I'm speaking in abstract units - the actual amount of energy borrowed varies depending on the fluctuation of space). Space is now down those two units of energy, and since the particles didn't come back together to release the energy, the black hole must give up some of its energy to restore back the two.
Since the sum of matter and energy within the black hole has been decreased, the black hole will decrease in size over time, and eventually the gravity will go low enough that light will be allowed to escape again. This would take a really really long time though. Eons. So we'll never likely be around long enough to see what's inside. But as I said from the beginning, black holes aren't exactly black. They actually emit energy. Just like a star. The difference is that they emit so little energy that it is insignificant. Thus, they are still extremely hard to find.
How we find them is a topic for another day.