The clock paradox is more often referred to as the twin paradox. It, like all paradoxes in science, comes about due to a lack of applicability of a theory to a particular experiment.
The twin paradox is based on the verified fact that the faster an inertial reference frame (IRF) moves, the slower time passes in said IRF from the point of view of someone outside of the IRF. This can be thought of in the following way. You are standing on the side of the road and a friend is driving past you in a car. The car is moving very fast, say 90% of the speed of light (0.9c, in the parlance of physicists). If you, on the side of the road, look at a clock in the car, you will see that 'one second' in the car takes more than 'one second' on a watch on your wrist.
However, one of the postulates of the special theory of relativity is that the *uniform motion* of a reference frame (that is, constant velocity, so no speeding up or slowing down or even changing direction) will not affect any experiment you do. This boils down to saying there is no way for you to do an experiment to determine if you are moving one way or if the rest of the Universe is moving the other way. So, this means your friend in the car would say (s)he is sitting still and you are moving at 0.9c in the opposite direction. Therefore, from your friend's point of view, 'one second' on your wrist-watch takes more than 'one second' on the car clock. Both of you say the other's clock is moving slower than your own. The thing is, the time dilation, as it is called, is not limited to clocks. It affects everything in the other frame, except the speed of light. In particular for this discussion, all biological processes (breathing, heart rate, thought processes, digestion, etc.) are slowed in the moving frame when viewed from the outside frame.
Now, let's think about a set of twins, one of whom (Terrence) wants to stay on Earth while the other (Estelle) wants to explore the near stars. Estelle gets on a ship and travels to a nearby star system at 0.9c. Once she gets there, she stops, has lunch, looks around, and decides to head home. So, she flies back to Earth at 0.9c. The question is, what is the age difference between the twins when they are reunited?
From Terrence's point of view, Estelle was moving at 0.9c toward the other star for a bit and 0.9c toward the Earth for a bit. As Terrence looks at Estelle's clock he would say her clocks were moving slower. Therefore, she was aging slower and she should be younger than he. From Estelle's point of view Terrence and the entire Earth was moving away from her at 0.9c for a bit and then was moving toward her at 0.9c for a bit. Estelle would say that as she looks at Terrance's clocks, his moved slower and therefore he should be younger. The 'paradox' comes in because both claim the other should be younger, which clearly cannot be the case.
The way out of this problem is recognizing that we have extended special relativity beyond its limits. The 'special' comes in because this theory only deals with uniform motion (see * above). Estelle was not always in uniform motion. At the beginning of her trip she had to accelerate from rest to 0.9c relative to Terrence. Then, when she arrived at the other star, she again had to accelerate (commonly called 'decelerate' in everyday language) to stop at the star. Her return trip had two more acceleration regions. These regions of acceleration are not handled by the special theory of relativity. One needs the general theory of relativity to deal with accelerations. When this is taken into account, Estelle will be found to be younger at the reunion. You could say that Estelle knew she was the one that had traveled because she could perform experiments demonstrating that, for part of the journey at least, she was in a non-inertial reference frame.
Whenever you see a paradox in science you should get excited. It means you don't understand everything going on and there is a chance to learn something new. Isn't that what life's all about (besides doing the hokey-pokey and turning yourself around).