You said that every child of Adam is a sinner. Does that mean we are born with sin?
No. Muslims believe that every child is born in a pure, natural state. Left to their own, children will grow up instinctively seeking the one true God, Allah. However, environmental influences and parents turn a child away from the pure, natural state. A saying of the prophet, on whom be peace and the blessings of God, confirms this. It says that each child is born in a natural state just as, for example a baby animal is born without any brand on its body; then the owner brands it with his own mark. Similarly, parents too would give a newborn their own religious identity (see Sahih al-Bukhari, Arabic-English, vol.8, no.597 and Sahib Muslim, Eng. Trans. vol 4, no. 6423).
The saying "every child of Adam is a sinner" means that every human being is a sinner, sin being an inevitable outcome of a fallible human nature. No matter how righteous a person is, he or she may at times disobey God through ignorance or forgetfulness. The prophet, on whom be peace, meant to emphasize that the best person is the one who seeks forgiveness for his or her sins. Furthermore, he said that one who repents from sin is like one without sin. God says in the Qur'an that He will replace the evil deeds with good for those who repent, believe, and do righteous deeds (see Qur'an 25:70).
Another saying of the prophet indicates that God actually intended that humans will be a species that commit sins so they can turn to Him and He would forgive them (see Sahih Muslim, Eng. Trans., vol.4, nos. 6620-2). This is a much better explanation than the popular conception according to which God at first sees that humans are good, then God discovers that they are wicked and so, being sorry that He made them in the first place, God eventually decides to wipe them off the face of the earth; but then he changes His mind again and lets them eventually procreate and fill the earth although they are still sinful as ever. The better explanation is that God knew in advance that we would sin, and we turned out just the way God planned. God does not discover new things - He knows everything always.
So, simply put, the Islamic belief is that people are not born in sin but they will eventually commit sins for which they should sincerely repent, and God will wipe out their sins. People do not inherit sins. Sin is something you do wrong. You couldn't have done anything before you were born, therefore you were born without sin. The Qur'an teaches that God does not hold us responsible for what others did before we were born, and no innocent person would carry the guilt of another (see Qur'an 4:111; 6:164). This coincides with our own sense of justice. No one considers it right to blame children for the sins of their ancestors, or to punish the innocent so that the guilty may go free.