What does the Bible tell us about how people knew right from wrong before the Law of Moses? Before "Thou shalt not kill/steal/lie" was given through the Mosaic law, how did people know what was right from wrong? How did they know what sin was?

Clearly there are examples of people having some moral standard pre-law, like when Abimelech knew it would have been wrong to sleep with a man's wife, or Joseph saying that his brother's evil deed of selling him into slavery was turned into good by God.
Firstly, understand that men and women are made in the image of God, who by His nature defines 'goodness'.  There was always a 'law' before it was written on tablets of stone and given to Moses: God sets the standard of righteousness by what remains in accord to His nature and unrighteousness by what constitutes rebellion against His nature. To the extent that our first parents were cognizant of God's nature and their own, they would have had some initial knowledge of good.  From what follows, it appears they would have been entirely ignorant of evil and the only sense of anything that could be wrong was when:


  16 ...the Lord God commanded the man, saying, “You may surely eat of every tree of the garden, 17 but of the tree of the knowledge of good and evil you shall not eat, for in the day that you eat of it you shall surely die.” - Genesis 2:16-17 ESV (emphasis added)


So initially, the only 'knowledge' (non-experential so not full 'knowing') they had of wrong/evil was what God told them. Subsequently, they were able to discern what was right and particularly what was wrong themselves after bitter experience:


  4 ...the serpent said to the woman, “You will not surely die. 5 For God knows that when you eat of it your eyes will be opened, and you will be like God, knowing good and evil.” 6 So when the woman saw that the tree was good for food, and that it was a delight to the eyes, and that the tree was to be desired to make one wise, she took of its fruit and ate, and she also gave some to her husband who was with her, and he ate. 7 Then the eyes of both were opened, and they knew that they were naked. And they sewed fig leaves together and made themselves loincloths. - Genesis 3:4-7 ESV (emphasis added)


The serpent lied completely regarding the first part ("You will not surely die") but the second part was at least a half-truth ("You will be like God, knowing good and evil") - scripture affirms that their eyes were opened as per the name of the forbidden fruit - "the knowledge of good and evil".

With the multiplication of sin and corruption in the human race, we have become darkened in our understanding, so the faculty gained from Adam's rebellion has been imperfectly transmitted to subsequent generations, but it has still been passed on to some degree as per:


  14 For when Gentiles, who do not have the law, by nature do what the law requires, they are a law to themselves, even though they do not have the law. 15 They show that the work of the law is written on their hearts, while their conscience also bears witness, and their conflicting thoughts accuse or even excuse them - Romans 2:14-15 ESV


A Gentile who does not have the (Mosaic) law is perfectly analagous to a patriarch (or matriarch) before the (Mosaic) law was given. The knowledge of right/good has been passed down to a degree (though quite imperfectly) as we are still image-bearers of God (though corrupted), the experential knowledge of wrong/evil has been passed down generationally only too adequately as mankind are inheritors of the original sin in their very nature as children of Adam and expert practitioners in what is wrong, however this latter knowledge is not of itself any use as a moral compass unless we sufficiently retain the knowledge of good that gradually passes from the earth with each generation that abounds in wickedness. 

The (Mosaic) law was given to shine the light of God's righteousness in the hearts of those whose understanding had been darkened by generations of sinful rebellion and restore to a degree the knowledge of good - it was a stop-gap measure to restrain wickedness and school a people in their need for a new nature and a Saviour to purchase it for them, before a true (experiential) knowledge of good could be recovered through faith in Christ.

Disclaimer: I believe this perspective represents an orthodox Christian (those who would agree with the content of the early creeds - Apostle's, Nicene etc.) view, if you disagree, I would greatly appreciate your criticism as to where it may differ.