Ubuntu equivalent of Yum's WhatProvides, to find which package provides a file

I believe apt-file will give you what you want.

$ apt-file update
$ apt-file list mysqladmin
kmysqladmin: /usr/bin/kmysqladmin

$ apt-file search mysqladmin
autoconf-archive: /usr/share/aclocal/ac_prog_mysqladmin.m4
autoconf-archive: /usr/share/autoconf-archive/html/ac_prog_mysqladmin.html
bash-completion: /etc/bash_completion.d/mysqladmin
kmysqladmin: /usr/bin/kmysqladmin

$ apt-file search mysqladmin
mysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_health.xml
mysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_startup_variables_description.dtd
mysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_startup_variables_description.xml
mysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_status_variables.xml
mysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_system_variables.xml
mysql-client-5.1: /usr/bin/mysqladmin
mysql-client-5.1: /usr/share/man/man1/mysqladmin.1.gz
mysql-cluster-client-5.1: /usr/bin/mysqladmin
mysql-cluster-client-5.1: /usr/share/man/man1/mysqladmin.1.gz
mysql-testsuite: /usr/lib/mysql-testsuite/r/mysqladmin.result
mysql-testsuite: /usr/lib/mysql-testsuite/t/mysqladmin.test

I use dpkg -S filename for that. It can't search for files that are not installed on your system with it, but it's shipped in all dpkg distros by default while apt-file is not.

You also can look that up for files that are not installed on your system using http://packages.ubuntu.com/ website.