Depends on the server service, really.
For most, you can do the following (off the top of my head);
- run monitoring software like Nagios
to find any services not running
- verify that you have a good backup
of the system before doing the
upgrade; the backup should allow for
restoration from a complete server
- Test the service the server handles
(bring up a web page if it's a web
server, send an email to verify
- Check the logs on the systems
post-reboot for error messages.
You can't really fully test it or fully know if the system is working because bug fixes may create edge cases where it's not working properly under certain circumstances.
Do you mean instead that you want to verify that services are back up on servers after updates? In that case programs like Nagios should be perfect. Do you mean test that the servers are functioning appropriately? That to my knowledge means either writing your own test cases or manually testing since, for example, your web server may come up but it's doling out error messages because your database service that the web server relies on for your application is dead.
EDIT: Okay, NAGIOS can monitor at the service level; I mean that the services may be "there" but something is affected in a way that it's giving out errors, so relying on automation will give a false sense of security. We've had cases where our Cisco phone system (Callmanager) seemed to be working fine only to discover after a good length of time that certain voicemails weren't properly routing to the mail server; we didn't know until investigating users saying they were told they had voicemail they never got...automated monitoring of services would not catch this without specifically checking logs since everything on Callmanager said it was functional).
If you have a specific need or specific case you might want to narrow it down a little and see what hits you get here. I see a similar parallel in hardware; how can I verify that my upgraded memory is working in my computer? "Boot it up and use it." Doesn't mean you're not going to see weird crashes because the memory isn't quite seated properly or has a tiny manufacturing defect that shows up at a particular temperature range, however.
This is another reason to consider virtualization. You can minimize impacts of upgrades, make it easier to recover from issues, and compartmentalize services more easily to individual servers (web server handles web tasks, etc.) as well as monitor disk use and network use to get a picture of the health of your servers a little more easily. Just throwing that out there as something to consider should the opportunity arise :-)