A catch-22 is a logical conundrum in which someone is essentially trapped, no matter what decision is made. For example, many entrants to the job market discover that you cannot get a job without experience, but if you have no experience, you can't get a job. This is a classic example of a catch-22, because the job-seeker is trapped in a circular logic paradigm with no way out.
The term was coined in 1961 by author Joseph Heller in the novel of the same name. In the novel Catch-22, one of the characters is trying to get out of service as a military pilot, and he learns that with a letter from the flight surgeon which states that he is insane, he will be excused from duty. However, he must approach the flight surgeon for the letter, and logic suggests that someone who is insane would not be aware of the fact, so by going to the surgeon, the character would prove that he was, in fact, sane. Whether or not he goes to the surgeon for a letter, his position as a pilot will not change.
Rules and regulations sometimes have catch-22s, either intentional or otherwise. Many people who have battled bureaucracy have noted that some agencies, especially government agencies, seem to delight in creating catch-22s. For example, you can't get many forms of identification without a birth certificate, but in order to get a copy of your birth certificate, you often need a form of identification. A catch-22 can also crop up in a set of standardized procedures, in which case it may not always be explicitly stated.
This logic trap has frustrated many people at some point in their lives, because it forces the victim to attempt to find an exception to the catch-22 so that he or she can defeat the logic trap. When a catch-22 is a bureaucratic problem, sometimes befriending someone at an agency can help, as he or she may be able to assist with the problem. Secretaries in particular can be gatekeepers of valuable information, and a little courtesy goes a long way with office staff.
You may also hear a catch-22 described as a situation in which someone is “darned if she does, and darned if she doesn't.” One could also consider this logic trap to be something which traps someone between a rock and a hard place, because no matter what decision is made, even if the decision is to do nothing, the outcome will be undesirable.