Hyrule Historia (Glitterberri translation) said:
•The City in the Sky
The city floating in the sky is the remnant of an ancient civilization that once flourished. It once had a close relationship with the royal family of Hyrule, but today the only messenger who remembers the lore left is Impaz. Its relation to Skyloft of the Sky Era is unknown.
Based on the above passage, I think it is likely that the City in the Sky (CitS) was built sometime between
Skyward Sword and
Ocarina of Time. I have no idea why it would be built during this time, but another poster in this thread brought up an interesting theory:
[...]But I was thinking that maybe Skyloft lost its power to float, so they put the propellers and started making the buildings and stuff. I think the Oocca are just some weird looking chickens, I think the Skyloftians either died out or went below the clouds and abandoned the city and that's why it is in ruins.[...]
In addition: Those who built it probably wanted to stay in the sky, while the others chose to settle on the world below. The CitS's technological design might have been facilitated by the Ancient Robots (judging from SS, Ancient Robots can be repaired). This could account for the many propellers and such. And it may be far-fetched, but Gonzo the Mechanic also comes to mind, and he may have helped construct it somehow. Also, for you timeline enthusiasts who abide by the
Hyrule Historia timeline, I think you might want to look into the placement of the
Minish Cap, and the Cloud Tops that appear in said game, as a connection might exist between it and the CitS.
Regarding the Ooccoo: To be honest, I think the Ooccoo were just thrown in the game to confuse us; their true purpose might have been to add a "wtf-factor" to the whole history and legend behind the CitS. [I've seen this done in other forms of media - novels, etc.] They probably had nothing at all to do with the CitS's sophisticated design and technology. It is more probable that the Ooccoo simply moved in after it was deserted by the original residents, or they were probably the pets of those residents.
Going out on a limb here, but another thing could be that the Ooccoo are the Ancient Robots. I know what you're thinking, "That doesn't make any sense; how could they have just transformed into the Ooccoo?! D:" (My statement was not to be taken literally) But as weird as it may seem, the
depiction of the Ancient Robots might have simply changed over the many years (possibly centuries) of time,
as legends often do.
Whatever the case, it seems Nintendo has left yet another loose end in the series, and it was likely done on purpose. It seems they are afraid of "running into a wall" in terms of creativity if too many connections are established between the games.