How is methylation of DNA done? I don't mean the chemical process of methylation, but rather how methyltransferase recognise the nucleotides (or the regions of nucleotides) which should be methylated?

The short answer is that we don't really know. This is an area of active research and a straightforward answer isn't clear yet. Have a read of this:
http://www.news-medical.net/life-scienc … ation.aspx