I've posted a short note on this topic almost exactly ten years ago, and it's time for an update. The situation: you've heard or read about a certain tool and want to install it, but you can't find it no matter how hard you try.
My first advice: don't search and install via graphical applications. ”Software centers” popular in consumer distributions may not show command line applications at all, so if you've read my last post and search for dc, you won't find what you are looking for.
Second: not every command comes in a package with the same name. For example, in Archlinux, dc is bundled with bc, and it is the latter (much more popular) application which gives the package its name.
To master such situations, it's time to leave graphical software centers behind and to learn a few basics about the actual package manager underneath. As an example, I'm showing a search for dig and drill, each of which is contained in a differently named package, with the name of these packages depending (as always) on the distribution.
pacman -Fs dig bind-tools pacman -Fs drill ldns
wajig whichpkg /usr/bin/dig dnsutils wajig whichpkg /usr/bin/drill ldnsutils
yum/dnf provides /usr/bin/dig bind-utils yum/dnf provides /usr/bin/drill ldns