Histone methylation is believed to play important roles in epigenetic memory in various biological processes. However, questions like whether the methylation marks themselves are faithfully transmitted into daughter cells and through what mechanisms are currently under active investigation. Previously, methylation was considered to be irreversible, but the recent discovery of histone lysine demethylases revealed a dynamic nature of histone methylation regulation on four of the main sites of methylation on histone H3 and H4 tails (H3K4, H3K9, H3K27 and H3K36). Even so, it is still unclear whether demethylases specific for the remaining two sites, H3K79 and H4K20, exist. Furthermore, besides histone proteins, the lysine methylation and demethylation also occur on non-histone proteins, which are probably subjected to similar regulation as histones. This review discusses recent progresses in protein lysine methylation regulation focusing on the above topics, while referring readers to a number of recent reviews for the biochemistry and biology of these enzymes.