I didn’t know that, though I admit the only time I ever hear it are in over-the-top stereotypical depictions of the French (France) either in English or Québecois French comedies. It’s “cliché France”, I guess. I don’t recall hearing anyone swear in French the last time I was there, but it’s not like I was listening for it, either! 
Specifically [post=261559]this post[/post] by bibliophage. Summary: according to the Trésor, it’s made of ‘z’ + ‘ut’. The origin of ‘ut’ is obscure but it may be a deformation of foutre (to fuck) or the first word of Ut tibi prosit meri potio, a sentence that was used by printers to wish good luck to each other. The ‘z’ was added after people liaised with ‘ut’ a preceding word ending with ‘s’. It’s the same process that lead to Ned and Nancy being nicknames for Edward and Anne in English. (“mine Edward” –> “mine Ed” –> “my Ned”)
That’s the common explanation I learned too at school. But what I had also learned back then (not saying it still holds today), was that Dieu was used greatly in swearing, and, at one point, it came to be seen as blasphemous to use Dieu/God in swearing, so a language shift was made and Dieu was replaced with Bleu*.
*BTW, aristocrats in France were said to have “sang Bleu” in their veins (I guess back then it was read both as metaphorical and somehow real), meaning they had God’s blood, and thus were fit to reign. Like the King being personally mandated by God.
Isn’t that what blasphemy means to begin with? Using god’s name in vain?
Yeah, but they thought they could pull it off because they were French.