Just ran into this issue myself.
Normally, the Debian (apt) installation stuff installs the software including some basic defaults. The install script asked if it should configure apache2, so it seems this is a bug, since when I got done, gornicht.
Everything else looked good, from phpinfo on. Searching failed to reveal any signs that phpmyinfo was installed in apache2, while MySQL had the appropriate changes.
My solution was as simple as
ln /etc/phpmyinfo/apache.conf /etc/apache2/sites-enabled/001-phpmyinfo
This hard links the default configuration from phpmyadmin's directory over to Apache2's.
(Obviously, if you're running lighttp or apache 1, targets and destinations must change.) This adds the phpmyadmin "site" to the list that Apache2 serves. You should look at it for edification.
Anyhow, after that,
sudo apache2ctl restart
sudo mysqld restart
should probably get http://localhost/phpmyadmin
working as expected.
(By all means, toss out constructive criticisms. I'm no expert on this.)
Not Found The requested URL /phpmyadmin was not found on this server. Apache/2.4.7 (Ubuntu) Server at localhost Port 80
mysql -u root -p
?sudo mysql_secure_installation
?