The expression is often used to  describe the quandry of being faced with two unacceptable choices. The Phrase Finder, one of my favorite sources for explanations of meaning and origin of expressions, says that the Committee to Ascribe a Nautical Origin to Everything (CANOE) tried unconvincingly to say it originated with something to do with ship maintenance. More logical is that it came from Greek mythology when Homer’s Odyssey refers to Odysseus being caught between the six-headed monster Scylla and Charybdis, a whirlpool. (Note that the word “Blue” was added when Cab Calloway recorded the song in 1931.)