So, this probably has a more modern explanation, but I remember learning about an Ancient Greek play, The Birds, which references a “cloud cuckoo land.” Why do we use it today? Probably one of those Victorian era cultural things that caught on.

Edit: A quick search seems to corroborate this. Also maybe the inspiration for being on “cloud nine.”