Cloud originally meant 'hill; mass of rock or earth'. At some point in Middle English people started calling those things in the sky clouds because they look like big hills or masses of water vapor. (The Old English word for 'cloud' was weolcan, which is cognate with the modern German Wolke.)
Cloud is also related to the word clod, which was originally a variant form of the word clot, which meant a lump or mass of something that had conglomerated or congealed. These words are also related to clay and trace back to the Proto-Indo-European root *glei-, meaning 'clay' and also forming words meaning 'to stick together'.
Some other words that come from this root are cleave (the one meaning 'stick together', not the homophonous but antonymous word meaning 'split apart'), clam (originally meaning a thing that stuck fast and later a specific kind of shellfish), climb (from the notion of sticking or holding fast to the thing being climbed), clamp (which arose as a variant form of the old past-tense form of climb, clamb), glue, gluten, glia (the cells that act as the glue of the nervous system), and colloid (because elements in a colloid are "stuck" together).