The PyBlosxom plug-in registry lists pymarkdown.py, by Tollef Fog Heen as a PyBlosxom plug-in. Odd thing is that the downloaded file seems to implement Markdown just fine, but not the PyBloxsom plug-in API.
So I hacked up this script that does so. It's basically http://err.no/pymarkdown/pymarkdown.py with the PyBlosxom plug-in stuff implemented. I'm truly a Blosxom newbie and I just did a cut&paste+hack from other plug-ins I saw, but it seems to work for my blog.