Você precisa citar o constructo que contém > porque é um caractere especial do shell, como este:
find / -name "*.md" -type f -exec sh -c 'markdown "$0" > "$0.html"' {} \;
Isso também renomeia os arquivos para que você tenha foo.html em vez de foo.md.html :
find / -name "*.md" -type f -exec sh -c 'markdown "${0}" > "${0%.md}.html"' {} \;