The etymology of "Wolke sieben" is closely related to the "siebenter Himmel" an ancient concept which is said to go as far back as to Aristotle who described seven vessels holding the seven heavens, and even back to Mesopotamian religion:
Sumerian incantations of the late second millennium BCE make references to seven heavens and seven earths. One such incantation is: "an-imin-bi ki-imin-bi" (the heavens are seven, the earths are seven.)
However the proverb "auf Wolke sieben schweben" is much younger than that. There are only references in publications beginning from the late 20th. Century. The earliest I could find is from a 1990 Hohlspiegel quote, but this is a satirical column of the German magazine "Der Spiegel" dedicated to style fails.
Die Hamburger Morgenpost zur ZDF-Talkshow "Live": "Zwischen Lafontaine und Röller saß Monika Hohlmeier als Weltkind der Mitten. Ihr Vater Franz Josef Strauß, falls er auf Wolke sieben fernsehen kann, wird seine Freude an ihr gehabt haben."
Another quote from "Die Zeit" dates later, in 1991:
Anderthalb Monate schwebte ich über dem Boden, jeden Abend, vor Tausenden von Menschen. Und dann bin ich aus Wolke sieben in die Müllkippe gefallen.
This may give a hint on the approximate date when it came up first. It may be a quote from a famous author but sadly I could not find a reference.