I just got this working so I figured I'd share what I found, since there's hardly any information about this anywhere online except an RFC, the GPG mailing list and one tutorial from the GnuPG blog.
You can use automatic key discovery with WKD (Web key directory) to make it easy for users to import your key, in GPG since version 2.1.12. Since this feature is fairly new, it isn't yet available in the current LTS release of Ubuntu (16.04; xenial), however it is available in Debian stable (stretch).
I couldn't add a DNS CERT or DANE / OPENPGPKEY record through my email service (which also hosts my nameservers). I tried making the PKA record - a foo._pka.example.com TXT record but GPG doesn't seem to recognize it and fails; I'm still investigating why.
So the last option for self-hosted auto-discovery was WKD.
First thing I had to do was add an email address to my key. My primary UID is just my name so the key represents my identity rather