A paradox is literally two contradictory things happening at the same time. I'll try and explain the "liar" thing a bit better.
A Cretan says "All Cretans lie all the time"
This statement has no truth value until you give it one, so let's do that. Let's assume that the statement "All Cretans lie all the time" is the truth. However, since this statement (which is true) is said by a Cretan, it must be a lie, and so it must actually be false. So Cretans do not lie all the time. However, since the statement is now false, and still said by a Cretan, it means it could be true. (Repeat forever).
The statement is both true and false at the same time, and therefore a paradox.
A Cretan says "All Cretans lie all the time"
This statement has no truth value until you give it one, so let's do that. Let's assume that the statement "All Cretans lie all the time" is the truth. However, since this statement (which is true) is said by a Cretan, it must be a lie, and so it must actually be false. So Cretans do not lie all the time. However, since the statement is now false, and still said by a Cretan, it means it could be true. (Repeat forever).
The statement is both true and false at the same time, and therefore a paradox.