One tool used widely at Yahoo is pogo, which is a massively parallel ssh-based execution tool. It can be used to invoke commands in parallel on thousands of machines at once. Pogo also contains a constraint mechanism to say things like "only run on 20% of this type of server at once". There's also a pre/post hook and recipe mechanism in pogo to perform custom check and command before and after a push. One way this is used frequently is to run health checks which verify that services on a machine come back up after a software push.
A similar tool that others use is Capistrano. I don't know a lot about it but that tool gets mentioned a lot.
Many people use the remote execution facility in their configuration management tool to accomplish this task as well. This can be done for example with Puppet or Cfengine or Chef. Those solutions tend to work ok at smaller scales. At larger scale (thousands of servers) you should really look in to a more specialized tool like the ones I've mentioned above.
Of course you can also use tools like ClusterSSH to accomplish tasks like this, although I recommend against that approach because it's not really scriptable or repeatable.