Notifications are sent by a standard hook, which on my Debian system is in /usr/share/pyshared/hgext/notify.py
. It doesn't contain any code to send coloured mail. You could either take a copy and modify it to do colouring, or write a new hook. That could be a shell script using:
hg diff --color=always
or you could use the Mercurial Python API.