It really depends just how far back you are, and how many Civs are building the ship.
If you still need a lot of techs, it's going to be hard to hinder opponents' ships much. Spies can do great things, but you really need a huge treasury to use them, the kind of treasury you can really only build and maintain by turning Science way, way down.
Get your spies out so you know where key parts are being built. Once the AI starts building a part somewhere, it will try to finish it there, regardless of how slowly it's being built. You can really put a huge damper on their efforts by bombing that city's improvements into the Stone Age and intermittently using Spies to destroy what progress they have made. I had one Emporer game where my only hope to win was by building massive bomber fleets, stationing them in the cities of weaker, friendly Civs near my stronger opponents, and bombing the crap out of everything they had. I took out every tile of Aluminum to slow their production of space ship parts to half, and then bombed/sabotaged improvements for the 40-50 turns it took me to get my ship off the ground and win.