The story
From double (“twice, i.e. more than”) + Dutch. For sense 1: Dutch (which historically had a wider meaning) as a foreign language was not easily understood, so anything completely incomprehensible would be double Dutch, i.e. twice as hard as Dutch. Sense 2 expands on this meaning.
Etymology from Wiktionary, CC BY-SA 4.0.