See the relevant RFC for the background.

Here's how I implemented this for my Debian server, with Bind9 handling my DNS:

  1. Generate the DNS records by typing this at a shell prompt on the system whose fingerprints you want to publish (make sure you include the trailing dot after the hostname): 
    ssh-keygen -r thehostname.thedomain.wherever.
Enter file in which the key is (/home/david/.ssh/id_rsa): /etc/ssh/ssh_host_dsa_key.pub

ssh-keygen -r thehostname.thedomain.wherever.
Enter file in which the key is (/home/david/.ssh/id_rsa): /etc/ssh/ssh_host_rsa_key.pub
  2. The above will print two records, each a line beginning "thehost.thedomain.wherever IN SSHFP". Paste them into the Bind9 zone file on the primary DNS server for the relevant domain/subdomain, each on a new line.
  3. Reload Bind9 service on the DNS server by typing 
    sudo /etc/init.d/bind9 reload

Before:

$ ssh jasper.dnorth.net
The authenticity of host 'jasper.dnorth.net (67.207.132.102)' can't be established.
RSA key fingerprint is 40:0d:3b:42:ff:4a:86:31:66:1b:9f:43:9d:f7:69:79.
Are you sure you want to continue connecting (yes/no)?

After:

$ ssh jasper.dnorth.net -o VerifyHostKeyDNS=yes
The authenticity of host 'jasper.dnorth.net (67.207.132.102)' can't be established.
RSA key fingerprint is 40:0d:3b:42:ff:4a:86:31:66:1b:9f:43:9d:f7:69:79.
Matching host key fingerprint found in DNS.
Are you sure you want to continue connecting (yes/no)?

Note that you have to force the OpenSSH client to check for the key in DNS with the -o VerifyHostKeyDNS=yes option, which you can of course put in your ~/.ssh/config file too - see "man 5 ssh_config" for more.

Note also that PuTTY has yet to implement the RFC, as per this page, and I agree with their doubts over whether it's worth any immediate attention. Still, it's quite nice to have around as an extra layer of reassurance.