A paradox is an apparently true statement or group of statements that seems to lead to a contradiction or to a situation that defies intuition. Typically, either the statements in question do not really imply the contradiction, the puzzling result is not really a contradiction, or the premises themselves are not all really true (or, cannot all be true together). The recognition of ambiguities, equivocations, and unstated assumptions underlying known paradoxes has often led to significant advances in science, philosophy and mathematics.
The word paradox is often used interchangeably with contradiction; but where a contradiction by definition cannot be true, many paradoxes do allow of resolution, though many remain unresolved or only contentiously resolved (such as Curry's paradox). Still more casually, the term is sometimes used for situations that are merely surprising (albeit in a distinctly "logical" manner) such as the Birthday Paradox. This is also the usage in economics, where a paradox is an unintuitive outcome of economic theory.
The paradox, "If you want peace you must prepare for war" is based on the premise that peace brought about though conflict is more long-lasting than peace brought about any other way; the paradox comes from the fact that peace is supposed to prevent war, but war seems to be the best way to truly obtain it. This paradox is more of a moral paradox than anything.
Another much more physical paradox (in the sense that it may in fact be impossible due to certain laws of the universe), is what's known as the grandfather paradox, whereby travelling back in time and killing your own grandfather before he was to meet your grandmother is impossible (following the laws of determinism). If you were to go back and kill him, he would never meet your grandmother, your mother/father would never be born, therefore neither would you, and therefore, you would never have been able to go back in time to kill him, so in actual fact, he would have met your grandmother, your mother/father would have been born, and therefore so would you... And of course, then you're free to go back and kill him and start the loop over again.
For a much more complete list of paradoxes and more details on them, visit the source above.