[Fingolfin II]

Very interesting, Formendacil! I always thought Cirdan departed over the Sea with Galadriel and Co., but now I'm not so sure thanks to your well-structured argument. However, it says in the Prologue something to the effect that 'It is not known when Celeborn finally sought the Grey Havens and with him went the last memory of the Elder Days from Middle-Earth' (don't have the book on me; it went something like that though). Now, if this is the case that means that Cirdan must have already left Middle-Earth or 'faded away', if Celeborn was the last person who lived through the First Age to depart from Middle-Earth.

Back to orginal question, though. I'm sure Cirdan wasn't the only shipwright and that there were other Elves who had not yet departed Middle-Earth who could build Sam (and themselves too) a ship. Or perhaps a ship was already waiting for him, like narfforc has suggested. Remember, there was at least one person who we know was able to build a ship- Legolas. In the Appendices it says that after Aragorn died, Legolas built a grey ship in Ithilien, sailed over Rauros and thus passed over Sea and was rumoured to have taken Gimli with him.