For actually deploying our code, we use Capistrano, which we also use to run one-off tasks across machines. This pulls from our code repsitory, and each of our dev/staging/production environments know which version control branch to pull and deploy in that environment.
I've found the dpkg method to be very effective. You can sign the packages, mirror the repositories, and set up servers to automatically upgrade some/all of the packages via cron jobs.
Packages can be automatically generated by your continual integration system, which also has the nice effect of creating a fully-trusted and centralized deployment path, making it difficult to sneak in uncommitted changes and non-managed files, etc.
The packages themselves support complex dependencies, start/stop scripts, etc, and dpkg/apt-get themselves have been ported to non-Linux platforms.
Personally, I'd still like a more comprehensive centrally managed solution based around the packaging model (ie, each server runs a management agent that can install/remove/update packages, etc).
http://github.com/sunkencity/apt_fu/tree/master
it's really a quick hack, but it get's the job done.
Oh, and dependencies are great.
(#) Link has gone now, but available at http://web.archive.org/web/20060925094756/http://www.kclee.d...