The puzzle of Theseus's Ship is an ancient philosophical head-scratcher, that ask us to ponder this question: over time, all the timbers and parts and pieces of a ship are replaced. Is it still the same ship? (I recall hearing this asked about the ship of Ulysses/Odysseus, but apparently Theseus's boat is the canonical example.)
I've found that if you chase this question around and around enough, you eventually see that it's meaningless. We can agree that it's the same ship, or not, for different purposes. The sailor who says "I've sailed on the same same for twenty years!" is right, but so is the helmsman who complains "This is not the same ship since we replaced her rudder and sails and keel!" "Same" is an idea of convenience, a mental construct for sorting out the buzzy spiky world of sensory experience, not a deep truth.
This is, I think, essentially the Buddhist idea of sunyata ("emptiness").
The famous Heart Sutra tells us that everything is "empty", that Avalokitesvara (a.k.a. Kwan Yin, Kannon, Kanzeon, Kwan Seum Bosal) saw this and "overcame all pain". In his commentary The Heart of Understanding (which I cannot recommend highly enough), Thich Nhat Hahn points out that we have to ask, "Mr. Avalokita, empty of what?" The answer is that all things are empty of a separate self, empty of an existence separate from the rest of the world. The ship does not have a "self" separate from the boards and nails and rigging and crew -- and these elements are always changing.
And -- this is the really radical part of Buddhism, as I understand it -- the same is true for our "selves". This is the idea called anatman, "no self". I go around with the idea that there's a "me" separate from my body and my mind, that remains constant even as body and mind change, but 'tain't so, any more than there's a ship separate from the bits that make her up. If that sounds depressing, trying looking at it from a different angle: if there is no self separate from the Universe, that doesn't mean that you are nothing, that means that you are one with the whole Universe.
Consult your local Zen master for further enlightenment, because I want to move on to a fascinating example of Theseus's ship: that good old boat that every local kid visits on a school field trip, that National Historic Landmark, that Baltimore class-A tourist attraction, the USS Constellation.
There was a frigate, authorized in 1794 and launced on September 7, 1797, called the Constellation. This ship went to the Gosport Navy Yard in Norfolk, Virginia in June 1853, where it was "broken down". In 1854, a corvette (or "war sloop") called the Constellation came out of that same shipyard -- according to some sources, using timbers from the broken-up frigate.
Apparently, the question of whether the 1854 ship is the "same" as the 1797 has been tossed around for decades. Defenders of the "same!" theory point out that the frigate was never stricken from the Naval Vessel Register — a wooden, sailing man-of-war called Constellation was continuously listed from 1797-1955. Defenders of the "different!" point of view say that the sloop was a new design and was planned to be built even if the frigate had not been around.
I suppose a salty sea-captain Zen master might say, "If you say these ships are the same, thirty lashes with the cat o' nine tails! If you say they are different, thirty lashes with the cat o' nine tails!"