Stephen Daborn asked this question on my High Availability blog entry and I didn't get back before the post closed - sorry Stephen - been doing a lot of snow boarding recently.

Anyway its a good question and it deserves an answer.

The best thing to do is to read the readme that comes with any service pack, hotfix, patch or whatever.  For instance if you look in the readme for service pack 3a @ http://support.microsoft.com/default.aspx?scid=/support/servicepacks/SQL/2000/SP3ReadMe.asp#_installing_on_a_failover_cluster you'll see all the steps you need.  For additional information on installing SP3a on a failover cluster, see Knowledge Base article 811168 - this is also referenced in the readme.

Always read the readme as the instructions may change between patches.

It should be possible to keep the downtime to a minimum - most of the time you should find this no more than the time taken to failover to a patched node and not the time it takes to actually install the patch.