Apparently Ubuntu now has APT::Install-Recommends set to True by default. This happened in version 8.10 (Intrepid) and it results in that packages marked as Recommended are now automatically installed kinda like dependencies.
I guess that change can make sense on a desktop system, where it might be nice to by default provide the user with a few more useful features. Dealing with servers on the other hand I very much like to be in control of what and what not is installed.
My way of disabling the automatic installation of Recommends is to put this into /etc/apt/apt.conf.d/01ubuntu:
Disclaimer: I don’t know the APT layout of Ubuntu well enough to know if that is the best place to put those settings. All I can say is that for now it seems to get the job done.
Yes, I have made a mention about it in Launchpad (#316472).