Sleep plays a substantial role in daily cognitive performance, mood, and memory. The study of sleep has attracted the interest of neuroscientists, clinicians and the overall population, with an increasing number of adults suffering from insufficient amounts of sleep. Sleep is an activity composed of different stages whose temporal dynamics, cycles and interdependencies are not fully understood. Healthy body function and personal well being, however, depends on the proper unfolding and continuance of the sleep cycles. The characterization of the different sleep stages can be undertaken with the development of biomarkers derived from sleep recording. For this purpose, in this work we analyzed single-channel EEG signals from 106 healthy subjects. The signals were quantified using the permutation vector approach using five different-information theoretic measures: i) Shannon’s entropy, ii) MPR statistical complexity, iii) Fisher information, iv) Renyí Min-entropy and v) Lempel-Ziv complexity. The results show that all five information theory-based measures make it possible to quantify and classify the underlying dynamics of the different sleep stages. In addition to this, we combine these measures to show that planes containing pairs of measures, such as the plane composed of Lempel-Ziv and Shannon, have a better performance for differentiating sleep states than measures used individually for the same purpose.