Well, a crystal is a repeating arrangement in space where each atom occurs in certain regular positions in the crystal structure. If you look along any direction in the crystal the crystal lattice is repeating and predictable. A time crystal is the same idea but it is repeating in the direction of time. For instance any shape that changes but repeats that same pattern over time in a regular and ordered way would be a time crystal.
I'm sure this is a simplification. For instance, I suspect a simple mechanical device (such as a clock) wouldn't constitute a time crystal any more than a tank full of loose balls would constitute a spacial crystal. In fact, I suspect the time crystal would need to be self organising in the same way that a spacial crystal self organises. In other words, the time crystal cycle is self perpetuating, hence the link to perpetual motion and the rather uncomfortable feeling that something might not be correct in the theory. In a spacial crystal it is the charges in the atoms and ionic bonds that self organise the crystal. For a time crystal (and I'm speculating here since I haven't read the arXiv article), maybe the transfer of energy or spin around the crystal would self organise the time crystal.