The march of the Kyreioi, later known as the Ten Thousand, was certainly a well-known story. The survivors spent at least 5 years in Spartan service upon their return, fighting in Asia Minor and mainland Greece, which would have allowed their tale to spread. When the mercenary army was disbanded, they presumably scattered to all corners of the Greek world, taking their considerable loot and tall tales with them.

Xenophon wrote the account that makes the march famous to us, and it was widely circulated by the middle of the 4th century BC. It has been argued that the Anabasis was not the only account of the campaign, and that Xenophon's work was at least partly polemical, trying to restore the author's reputation against the accusations of another author (Ephoros, or possibly Sophainetos, who was also a veteran of the march). If this is true, it implies that the story was widely read and discussed among the elite.

We know that other Greeks knew the story, because they make detailed references to it. Consider Isokrates' speech encouraging Philip of Macedon to turn his eyes on Persia rather than making war on the Greeks:

I think that if any of the others should be prompted to advise you in favor of the expedition against Asia, they would resort to a plea of this kind: that it has been the fortune of all who have undertaken a war against the King, without exception, to rise from obscurity to brilliant distinction, from poverty to wealth, and from low estate to be masters of many lands and cities.

I, however, am not going to urge you on such grounds, but by the example of men who were looked upon as failures: I mean those who took the field with Kyros and Klearchos.

Every one agrees that these won as complete a victory in battle over all the forces of the King as if they had come to blows with their women, but that at the very moment when they seemed to be masters of the field they fell short of success, owing to the impetuosity of Kyros. For he in his exultation rushed in pursuit far in advance of the others; and, being caught in the midst of the enemy, was killed.

But the King, not withstanding that his foes had suffered so severe a loss, felt so thorough a contempt for his own forces that he invited Klearchos and the other captains to a parley, promising to give them great gifts and to pay their soldiers their wages in full and to give them safe convoy home; then, having lured them by such prospects, and having assured them by the most solemn pledges known to the Persians, he seized them and put them to death, deliberately choosing to outrage the gods rather than risk a clash with our soldiers, bereft though they now were of Kyros's aid.

And what challenge could be nobler or more convincing than this? For it is evident that, if it had not been for Kyros, even that army would have overthrown the power of the King. But for you it is easy both to guard against the disaster which befell at that time and to equip yourself with an armament much stronger than that which defeated the forces of the King. How, then, since you possess both these advantages, can you fail to undertake this expedition with all confidence?

-- Isokrates 5.89-92

Xenophon's exploits eventually inspired Alexander the Great to try his hand at conquering the Persian empire, and so it befell.