The main reason for using Markdown is the readability of a marked text. For instance, you can send it in a plain-text email and the reader will still understand the emphiasis, bullets, the text will be divided in paragraphs et cetera.
When you ask about storing data, it depends. If you enable Markdown in Wordpress blog engine, it stores data as the user has input it - in MarkDown. In StackOverflow, however, it seems like the data is stored as HTML. At least, the "SO Dumps" contain HTML, not markdown (at least, people are complaining that they have to convert it back)
If you use WMD editor, you can show the user how the outputs will look like after being converted to HTML. Even though Markdown syntax is really simple, it is not hard to make mistakes. Hence, it is best to show users the output.