”over the clouds” means a trajectory, does it not? Über den Wolken is a position. The corresponding trajectory (to a place above the clouds) would be über die Wolken, with the noun phrase taking accusative case instead of dative.
I think it can be either -- The lamp is hanging over (= above) the table / The bird is flying over the table.
Actually Über den Wolken is also a famous song by a singer called Reinhard Mey :) It talks about watching a plane start and wishing to fly as well:
“Über den Wolken muss die Freiheit wohl grenzenlos sein. Alle Ängste, alle Sorgen – sagt man – blieben darunter verborgen, und dann würde, was uns groß und wichtig erscheint, plötzlich nichtig und klein.”
“Above the clouds freedom must know no bounds. All our fears, all our worries – they say – would stay hidden below them, and then what seems big and important to us would suddenly become trifling and small.”
Thank you for that lovely song, that's a fantastic way of learning a language, do give examples like that whenever you have the chance.
I agree that "over the clouds" sounds more like it's accusative than "above the clouds," but I also agree with mizinamo, that "over the clouds" could also be dative, either "die" or "den" in this sentence.
It depends on what you mean.
If you mean that the birds are flying and the clouds are beneath them the whole time, then Die Vögel fliegen über den Wolken.
If you mean that the birds are flying, see a cloud, go up so that they are above the cloud and then go down again once they have crossed the cloud, then Die Vögel fliegen über die Wolken.