This presentation is a modified version of Russell's original presentation.
There once was a platoon of men who were very punctilious about following orders. One day, the commander decided that the men needed to look less disheveled. One of the men, a barber named Bob, proposed that he shave everyone everyday. Some of the men complained and asked if they could shave themselves instead. As a compromise, the commander ordered Bob to shave all and only the men who do not shave themselves.
The paradox is this: who shaves Bob? If he shaves himself, then he ends up being prohibited from shaving himself. In which case he must shave himself. Continue ad infinitum.
The significance of this paradox was that it undermined the existence of certain types of sets, potentially undermining all of set theory. There were some interesting responses, but ultimately Gödel showed the inescapable nature of such paradoxes for most logical systems.