For ubuntu, installing pandoc can get big. This is the minimum footprint method I found, while still getting all that latex goodness in your installation.
sudo apt-get install pandoc texlive-latex-base texlive-fonts-recommended
Then, just go pandoc what.md -o that.pdf and you get fancy.