I realized this morning while taking a rare shower that, despite being able to at least pass for a materials scientist sometimes, I have no damn clue why and how soap cleans such a wide variety of stuff.
The answer (thanks Wikipedia!) turned out to actually be kind of complicated, which made me feel better.
Soap, basically, is made by reacting a base (usually some kind of alkali salt) and some kind of fat, in a process awesomely called "saponification". The type of base used in the manufacturing determines the structure of the soap (NaOH will give you a bar of soap, while KOH gives you liquid soap).
The fat is the thing that does the actual cleaning work. When you mix soap and water, the fat disperses and forms little hollow pockets called micelles, which are hydrophilic (attracted to water) on the outer surface and lipophilic (attracted to various organic molecules) on the inner surface. Oil, grease, fats, and other stuff that ordinarily wouldn't wash away in water due to hydrophobicity (oil and water don't mix, remember?) will get trapped inside the micelles, which the water then easily washes away. So basically soap is a clever workaround to the fact that lots of lipid-based stuff doesn't mix with water. Somewhat counterintuitively (to me), the base part of the soap doesn't really have a lot to do with anything, since it's pretty dilute. It mostly just provides a matrix to store the fatty molecules in a stable state until they need to do their thing.
This is obviously a pretty oversimplified picture and probably wrong on some details, but you get the idea.