Suppose a man travels back in time and impregnates his great-great grandmother. The grandmother would thus give birth to one of the man's great grandparents, who would then give birth to his grandmother or father, who would then be able to give birth to one of the man's parents, and finally to the man himself. As a result, the man's very existence would be pre-determined by his time traveling adventure, and therein lies the paradox.
The classic example is shown in the movie Back to the Future. In it, Marty McFly (played by Michael J. Fox), travels back from the year 1985 to 1955, and prevents his parents from falling in love. This has the effect of causing himself to not exist. By the end of the movie, of course, he gets them back together and is able to save himself. The next two sequels deal with variations on the theme. Movies in the Terminator franchise also deal with predestination paradoxes, as do a few episodes of the Fairly OddParents cartoon series (namely The Secret Origin of Denzel Crocker and Father Time, wherein respectively, the show's main character causes his later teacher's findings on fairy godparents to become public, and sees how his parents met for the first time).
The Predestination paradox is very closely related to the Grandfather paradox. Please see that page for a more detailed analysis of possible genetic paradoxes posed by time travel.