Here is three years later updated answer, for others landing here from Google (like I did once):
Markdown on Save plugin, mentioned in Michal Mau's answers wasn't updated and supported for certain period of time. Now, it seems back on line. In the mean time, it has got a twin plugin, called [Markdown on Save Improved](Markdown on Save Improved), which offers more options.
However, this twin-plugin is no longer supported, in favor of Markdown module for Jetpack. So, if you're starting your yourney with Markdown today (middle of 2014), you should first interest yourself in Jetpack, which -- aside of Markdown -- will bring a lot of Wordpress.com goodies to your self-hosted blog.
Note, that Markdown on Save and Markdown on Save Improved extensions are often used with Markdown QuickTags extension, which gives user an abillity to use keyboard shortcuts, for example Ctrl + I for outlining selected text with
* * and thus making it written in cursive or Ctrl + B for surrounding it with
** ** and this making it bold.
Jetpack's Markdown module comes with a handy toolbar that replaces non-visual editor default toolbar with buttons corresponding to Markdown. However, at least in current version (Jetpack 3.0) it hasn't got any support for keyboard shortcut. So, if you prefer (as Markdown QuickTags's tagline says: "less clicking, more writing"), you need to fall back to Markdown QuickTags even though this extension wasn't updated for over two years and seems to be abandoned.