Their sons are carefully instructed from their fifth to their twentieth year, in three things alone---to ride, to draw the bow, and to speak the truth
How true is this statement by Herodotus, particularly the truth telling part? Why was Persia like this and what effect did it have on their society?
Ideologically, yes, telling the truth was very important. The idea of the "Lie" as a sign of evil and corruption was a key concept in Zoroastrian/Early Persian morality. When Darius produced the Behistun Inscription which justified his rebellion and becoming King-of-Kings, he wrote:
"Says Darius the king: This (is) what I did; by the grace of Auramazda it was (done) in every way; after that I became king, I engaged in 19 battles; by the grace of Auramazda I waged them and I seized 9 kings; there was one, Gaumata by name, a Magian; he lied; thus he said; I am Bardiya the son of Cyrus; he made Persia rebellious; there (was) one, Atrina by name, a Susian; he lied; thus he said; I am king in Susiana; he made Susiana rebellious to me; there (was) one, Nidintu-Bel by name, a Babylonian; he lied; thus he said; I am Nebuchadrezzar the son of Nabu-na'id; he made Babylon rebellious; there (was) one, Martiya by name, a Persian; he lied; thus he said; I am Imanish, king in Susiana; he made Susiana rebellious; there (was) one Phraortes by name, a Mede; he lied; thus he said; I am Khshathrita, of the family of Cyaxares; he made Media rebellious; there (was) one Citra(n)takhma by name, in Sagartia; he lied; thus he said; I am king in Sagartia, of the family of Cyaxares; he made Sagartia rebellious; there (was) one Frada by name, a Margian; he lied; thus he said; I am king in Margiana; he made Margiana rebellious; there (was) one, Vahyazdata by name, a Persian; he lied; thus he said; I am Bardiya the son of Cyrus; he made Persia rebellious; there (was) one, Arakha by name, an Armenian; he lied; thus he said; I am Nebuchadrezzar the son of Nabu-na'id; he made Babylon rebellious."
and also:
"Says Darius the king: These (are) the provinces which became rebellious; the Lie made them rebellious so that these deceived the people; afterwards Auramazda gave them into my hand; as was my will so [I did] unto them"
The "Lie" also appears in the Zend Avesta, the holy book of Zoroastrianism. For example, the Yasna mentions:
"Mindful of your commands, we proclaim words unpleasant for them to hear that after the commands of the Lie destroy the creatures of Right, but most welcome to those that give their heart to Mazda."
Of course, like all things in life, ideology and reality are two different things, and running an empire certainly requires a level of deceit and dissimulation. But in ethical terms it was fundamental
Sources
The Behistun Inscription:
http://mcadams.posc.mu.edu/txt/ah/Persia/Behistun_txt.html
The Zend Avesta: