Markdown is a great way of formatting text as it was intended to be convertable into HTML and yet be easy to read. It makes note taking a lot more fluid as you don't have to move a mouse to format.
Evernote already has the "---" markdown for horizontal rules. So I don't think it would be too hard to implement "*" for italics and "_" for bold. Also, "-" for bullet lists should be easy to do as well since there is the option to use "*" for bullet lists. However this clash would mean that it would have to be specified whether or not markdown is to be used when making the note.
I would use Evernote a lot more if there was support for markdown as it would mean note-taking on my mobile would be a whole lot easier.