We have only one source on this, Pausanias, a travel writer active in the 2nd century CE. He indicates that some went to Sicily and Rhegion (in Calabria), but most went to Hesperides in Libya (modern Benghazi).

Here's what he writes in his Guide to Greece 4.26.2, given here in a fresh translation:

When the Athenians' disaster at Aigospotamoi happened, the Lakedaimonians expelled the Messenians from Naupaktos, since they controlled the sea with their ships. Some of them migrated to their relations in Sicily and in Rhegion, but most of them went to Libya, and the Euesperitai in Libya. For the Euesperitai had been defeated in war by barbarian neighbours, and were inviting any Hellene to live there. Most of the Messenians went to them; their leader was Komon, who commanded them at Sphakteria.

Pausanias goes on to relate that Komon had a dream foreshadowing a brighter future; and that after Sparta was defeated in the battle of Leuktra (in 371 BCE) Thebes sent messengers to many places, including the Euesperitai, summoning Messenians to the Peloponnesos, thereby bringing on the Third Messenian War. Pausanias doesn't give specifics, but it may be that many or even most of the Messenians in Libya returned to Greece at that point.

'Euesperitai' appears to be a variant of Euesperidai (Herodotos), who lived in the the city of Hesperides in western Cyrenaica. The city was renamed Berenike in the Ptolemaic era, and is now Benghazi.