This is only partially answered Scripturally.
Genesis 25:1-2 (KJV)
25 Then again Abraham took a wife, and her name was Keturah.
2 And she bare him Zimran, and Jokshan, and Medan, and Midian, and
Ishbak, and Shuah.
The significance of this passage is that the Midianites were descendants of Abraham, and as such would have shared the knowledge of the God of Abraham. They aren't in the line of Isaac and Jacob, and clearly not in the chosen line, but they would at least have knowledge of the God of Abraham, Isaac, and Jacob.
I'm not overly fond of Wikipedia as a source, but from http://en.wikipedia.org/wiki/Midian:
The Midianites were the descendants of Midian, who was a son of
Abraham through his wife Keturah. This can be seen in the following
Biblical passages. Genesis 25:1-2 1Then again Abraham took a wife, and
her name was Keturah. And she bare him Zimran, and Jokshan, and Medan,
and Midian, and Ishbak, and Shuah. (King James Version)
The Midianites through their apparent religio-political connection
with the Moabites are thought to have worshipped a multitude of
gods, including Baal-peor and the Queen of Heaven, Ashteroth. An
Egyptian temple of Hathor at Timna continued to be used during the
Midianite occupation of the site. However, whether Hathor or some
other deity was the object of devotion during this period is
impossible to ascertain.
Therefore, even though the Midianites didn't worship the God of Israel, enough knowledge of Him must have existed among them for Jethro, Moses' Father-In-Law, to make the following statement after hearing about the Exodus, and God's miraculous freeing of the Jewish People from their Egyptian bondage:
Exodus 18:9-11 (KJV)
9 And Jethro rejoiced for all the goodness which the Lord had done to
Israel, whom he had delivered out of the hand of the Egyptians.
10 And Jethro said, Blessed be the Lord, who hath delivered you out of
the hand of the Egyptians, and out of the hand of Pharaoh, who hath
delivered the people from under the hand of the Egyptians.
11 Now I know that the Lord is greater than all gods: for in the thing
wherein they dealt proudly he was above them.
Based on the combination of these facts, it would appear that the Midianites, like all other cultures, turned away from the God of Abraham, unto false gods. Jethro, however, appears to have been made a believer in the God of Abraham after hearing of His miraculous works.