Well, the main story point is the flooding of the Mediterranean (revealed recently when the protagonists are shown a map of the projected sea level). We know that happened in the past and might happen again. People in the past had no way to produce such accurate maps. Also, the sand castle built in the beginning looks medieval, not prehistoric.

Update: the blurred dialog of the woman in the castle has been partially deciphered and also places the story in the future pretty clearly: http://www.explainxkcd.com/wiki/index.php?title=1190:_Time:_...