So the css used by the plug-in is actually called
demo.css - see file. ( I know, it started as that I've never got round to calling it something more appropriate). The plug-in requires more css that just prettify, however: for example to style the preview box, the toolbar etc. So just replacing the contents of demo.css with your prettify theme won't work.
demo.css there are two lines which contain the compressed prettify theme. You should be able to replace that with any theme you want...
However, you should never edit plug-in files directly. Though in this case unlikely - doing so can have unintended consequences. But more importantly your changes are lost when you update.
So here's a better way to replace a plug-in's css file.
- Copy the css file into your theme (rename it
wp-markdown.css, say - because that makes sense).
Make any changes to the copy in your theme.
De-register the default CSS and re-register your own copy
add_action( 'wp_enqueue_scripts', 'wpse82441_wpmarkdown_replacement_style', 20 );
wp_deregister_style( 'md_style' ); //Deregister the style
'md_style', //Re-register the style
get_template_directory_uri() . '/wp-markdown.css', //Point to the copy in your theme