I replaced the fan of my T60 just 2 days ago, I bought it from a longstanding member at Thinkpads forum. I was told it might or might not fit in my T60, turned out it didn't. Howerver, with the help of a youtube video I took the fan out of the heatsink assembly and put it in my old assembly, it actually worked! As for thermal paste/grease, you can get it cheaply from a hardware store or at eBay.
As previously mentioned, HMM and lenovo service videos are of great help, they make things extremely easy. It was my first fan DIY!