"Cycles" are CPU instruction cycles. Cycles per byte roughly measures how many instructions, in a given instruction set, are needed to produce each byte of output. They're a reasonably-good relative measure of the performance of different algorithms.
Generally, when you measure an algorithm's cycles per byte, you use carefully controlled conditions. You ensure the system isn't doing anything else, you ensure the code cache is populated, you try to avoid measuring memory speed, and so on.
Some ciphers are dependent on their data. To help control for this, you try to use a large data set and average it out.
You can't measure asymmetric ciphers this way, because they don't operate on bulk data. For them, it makes more sense to talk about cycles per operation, operations per second, or the like.
I noticed on that data set, they have a lower cycles per byte for SHA256 than SHA512. If they had used their CPU's 64-bit instruction set, the results would have been the other way around. So the results are heavily dependent on how the code is compiled (instruction set, optimizations, and so on).