How can I do this so that I don't have to go around and manually setup the printers on all the computers again?

If you do the domain dance that I mentioned (and that Andy correctly described), you would name the new server to be the same name as the old one (in addition to a domain dance you'd do a server name dance). You would then make the printer shares exactly the same names and the users would not only not have to do anything, they wouldn't even notice anything had changed.

Obviously this is a weekend project. I did this recently with our new departmental server and it went pretty smoothly. Of course, I was going from NT351->NT4 instead of 4->5, so I'm not sure if there are any "gotchas" in 4->5.