You unplug the old PC. Than you plug in the new one :-)).
Now seriously, I went through at least 2 projects like this one, and we are upgrading PC's in a continuoas basis as well. It really depend on how big of a network (I suppose it is a network) you are talking about (how many PC's), do you want to change OS, protocols any software on the system ..etc.
basically the best thing is to setup an initial PC with everything you need (basic setup), create an image (Norton ghost or something simillar) and just deploy that on every PC after that. You can setup all the new PC's and deploy them during a weekend or over a few days, or you can do one by one over a few weeks, again depending on the number we are talking about.
If you have "delicate" PC's (special applications, special hardware attached) I would leave those at the end and also make sure they are compatible with any new OS you might want to deploy. I had apps that worked under '98 but not under Xp so had to take special care of those.
Bottom line, although it takes more time, replacing PC's is way easier that replacing your server :-))