It was immediately clear that Dragon NaturallySpeaking was the only option for dictation software. Their product was miles ahead of others in voice recognition, but it only ran on Windows or Mac. Unfortunately I was never successful running Dragon NaturallySpeaking in Wine and had to settle for running in a Windows VM and proxying the commands to the Linux host.
I will leave out some of the configuration steps that I went through in this post. You can find detailed instructions on how to get everything up and running on my GitHub repo.