One-click rollbacks. It's really, really important that when you deploy a release to the production servers, you can un-deploy it with a single click or command. That means all changes should be logged, and all the old files should be kept around until the next release. You hopefully won't have to use this often, but when you do, it's a lifesaver to be able to say "Okay, we'll rollback and fix the problem at our leisure" rather than frantically trying to get the servers back online.
Staging/production configs. If you do need to have differences between staging & production configs, try to limit them to a single overrides file. This should not contain app config that changes frequently, and should be limited to things like debug options and Patrick's "don't e-mail all these people" flag. Check in both the staging and production config overrides, but don't check in the actual filename under which the system looks for them. On the actual machines, cp the appropriate config to the appropriate location, and then leave it there. This way it doesn't get blown away when you redeploy, and you don't need to manual work to update it on deployment. (I suppose you could have your deployment scripts take a staging or production arg and copy it over appropriately, but this is the poor-man's version.)
Deployment schedule. I'd really recommend having a set, periodic deployment schedule, maybe even run off a cronjob. The problem with manual deployments is they usually happen only when people get around to it, and by then, dozens of changes have gone in. If something goes wrong, it's hard to isolate the actual problem. Also, deploying infrequently is bad for your users: it means they have to wait longer for updates, and they don't get the feeling that they're visiting a living, dynamic, frequently-updated website.
The holy grail for deployment is push-on-green. This is a continuous-integration model where you have a daemon process that continually checks out the latest source code, runs all the unit tests, deploys it to the staging server, runs all the functional & integration tests, and if everything passes, pushes the software straight to the production servers. Obviously, you need very good automatic test coverage for this to work, because the decision on whether to push is completely automatic and is based on whether the tests pass. But it has big benefits for both reliability and morale as team size grows, and big benefits for users as they get the latest features quickly and you can measure the impact of what you're doing immediately. I believe FaceBook uses this system, and I know of one team inside Google that has the technical capability to do this, although in practice they still have some manual oversight.
Third-party software. I know Patrick recommended using apt-get, but I'm going to counter-recommend pulling any third-party code you use into your own source tree and building it with your own build tools. (Oftentimes you'll see all third-party software in its own directory, which makes it easier to audit for license compliance.) You should integrate in a new version when you have a big block of spare time, because it'll most likely be a long, painful process.
There are two main reasons for this. 1) is versioning. When you apt-get a package, you get the most recent version packaged version. This is not always the most recent version, nor is it always compatible with previous versions. You do not want to be tracking down a subtle version incompatibility when you're setting up a new server or deploying a new version to the production servers - or worse, when you rollback a change. (If you do insist on using apt-get, make sure that you specify the version for the package to avoid this.)
2.) is platforms. If you always use Debian-based systems, apt-get works great. But what if one of your devs wants to use a MacBook? What if you switch hosts and your new host uses a RedHat-based system? The build-from-source installers usually have mechanisms to account for different platforms; open-source software usually wants the widest possible audience of developers. The pre-packaged versions, not so much. And there're often subtle differences between the packaged versions and the source - I recall that PIL had a different import path when it was built & installed from source vs. when it was installed through apt-get.