How do I get a list of the packages that "provide" something (using dpkg or APT)

If you run apt-cache showpkg on a meta package, the "Reverse Provides" section will list all of the available packages that fulfill the given role. Using awk you can easily print out the list of packages that provide the given meta package.
Eg.
$ apt-cache showpkg telnet-client | awk '{if (f==1) print $1}/^Reverse Provides:/{f=1}' | sort
heimdal-clients
inetutils-telnet
krb5-clients
telnet
telnet-ssl

These meta packages are in strong relation with the symbolic links in the /etc/alternatives directory. If you install a package that provides a utility/binary for a meta package, then it will be added with a symlink to /etc/alternatives. You can list all of these "alternatives" (for the meta packages that already have a real package on your system) with update-alternatives --get-selections.