Thank you, oh great and mighty wizard! Indeed, apt-file was exactly what I was looking for.
It's a shame I now have to do separate updates for apt-get and apt-file. But no matter, I've added it all into my universal script that figures out what platform I'm on and does the right thing. The apt-get section is now complete.
I wish I had seen that Pacman/Rosetta page a couple years ago. I've already figured out most everything for the first three platforms. I've never used SUSE or Gentoo.