Markdown is a text-to-HTML conversion tool for web writers written by John Gruber. Markdown allows you to write using an easy-to-read, easy-to-write plain text format, then convert it to structurally valid XHTML (or HTML).
Thus, Markdown is two things: (1) a plain text formatting syntax; and (2) a software tool, written in Perl, that converts the plain text formatting to HTML. See the Syntax page for details pertaining to Markdown’s formatting syntax.
PHP Markdown is a port to PHP of the Markdown program by Michel Fortin. He even did an extended version called Markdown Extra to enable tables and other usefull things.