Thanks all for your help with this; I did the CPU upgrade today and it went smoothly!
Maybe this description will be helpful to someone else, even though the process is well documented here already!
I have a 2009 Mac Pro (flashed to 5,1) with originally 2 x 2.26 Quad Core Xenon processors. I bought two new X5677 3.46 Quad core Xenon cpu's on eBay for $25. I was able to de-lid them using the vise technique described in other threads here (very easy). Then I used masking tape around the edges of the cpu, put it back in the vise and using a single edged razor was able to carefully scrape off all the solder (at times it feels like you might be cutting into the cpu, but there's a lot of solder there and it's much softer than the metal on the cpu so it came off easily). I didn't do any sanding or further clean up because it seemed smooth, even though there was some marking or discoloration from the solder. I left the black rubber "frame" on as well, since it seems to be un-necessary to remove it.
Then I opened up the Mac Pro and removed the heat sink, and cleaned up the "grease" from the old cpu. This was a soft compound, easily removed with a credit card and some scraping. I did a final clean up with a few drops of "Arctic 1 Thermal Material Remover", wiping with a soft cloth. Next I inserted the new cpu, matching up the two notches on top and bottom, and replacing the black square spacer/ gasket. I put a small dollop of "Arctic Silver 5" Thermal compound on the cpu and then put the heatsink back on, and screwed it down. Then I took it apart again, to look at how the Thermal compound has spread out and if I had put enough on... it looked like I hadn't (it wasn't completely covering the top of the cpu, or maybe I hadn't screwed it down enough to cause the compound to squeeze out more?). I applied a little more Arctic 5. Repeated the same with the other processor and heatsink, and proceeded to tighten all screws to the point where I felt a strong resistance.
Plugged in the Mac Pro, started it up, and .......nothing! No chime, no startup. Panic!
Then I pulled out the tray again, loosening the screws about a half to three quarters turn, gave the heatsinks a little jiggle, gently, trying to seat them as best I could in case they weren't making good contact with the cpu. Plugged everything back in, started up, and got the chime and everything was normal!! Phew!! Success!!
Couldn't be happier with my Mac Pro, and for what it's worth has a Geekbench score of 2937 (single) and 19173 (Multi Core).
Thanks again to all posters here for the advice and help on the way!