Círdan is indeed very old, but when Gandalf first arrives in Middle-earth Círdan tells him,
my heart is with the Sea, and I will dwell by the grey shores, guarding the Havens until the last ship sails. [Of the Rings of Power and the Third Age]
Círdan was lord of the Falathrim and Ossë had long ago persuaded them to stay in Middle-earth. Círdan was of the Teleri, and during the Great March they were the slowest group. In Of the Coming of the Elves it is said of them;
they tarried on the road, and were not wholly of a mind to pass from the dusk to the light of Valinor. In water they had great delight, and those that came at last to the western shores were enarmoured of the sea.
Most of the stragglers who stayed behind in Middle-earth were Teleri.
When the West was open again at the end of the First Age the Teleri still stayed, even some of the Noldor.
not all the Eldalië were willing to forsake the Hither Lands where they had long suffered and long dwelt... Among these were Círdan the Shipwright [The Voyage of Eärendil]
Círdan had his reasons for staying based on some of the passages I cited. Middle-earth was home, he loved living by the shores, and he was convinced to remain as well. Generally he had the same pullings as his people, they loved water and tended to dwell by bodies of water, whether the sea, rivers, lakes, or falls.
Círdan himself never departed from Middle-earth before he finally left. The leaders of his people did, Elwe and Olwe, when they went as ambassadors to the West.