There was a great article on Domino upgrade in THE VIEW magazine (July/August 2008) by Jon Champlin.
For small and medium systems (up to 10000 users and 50 servers) it goes like this:
1. Upgrade Notes clients that administrator will use on the Domino Directory.
2. Upgrade admin server for DD.
3. Allow DD to replicate to all servers in the domain (DD design is backward-compatible).
4. Upgrade hub servers.
5. Upgrade mail servers.
6. Upgrade SMTP servers.
7. Upgrade application/web servers.
8. Upgrade third party product servers.
9. Upgrade all user Notes clients.
10. Replace the design of mail files with mail8.ntf.
Here are the steps for upgrading each Domino server mentioned above:
1. Shut down server cleanly.
2. Install Release 8.x of Domino.
3. Copy and customized templates into place.
4. Run the Design taks to refresh the design of system databases, which updates the design of names.nsf.
5. Run the Updall task.
6. Restart the server.
7. Proceed to the next server in the domain.
Hope it helps.