Turned so that the upper surface becomes the lower.
'Upside down' is one of a longish list of English expressions that refer to things being inverted or in disorder - 'topsy-turvy', 'head over heels' (even though that is the usual arrangement), 'arse over tea-kettle' etc. The mediaeval English also had the terms 'overset', 'overtumble' and 'topset downe', which have now gone out of use. Even the apparently unrelated word 'preposterous' was used in the Middle Ages with its literal Latin-based meaning of 'in the wrong order; inverted' (pre post, geddit?). This profusion of similar phrases suggests a widespread interest in the recounting of stories of people falling over - matched today by the popularity of home video television shows.
The interest is common in other languages too; the Italians have the word sottosopra, meaning upside down, upset, commotion (literally 'under over'); the French even have a specialist term for a sequence of stamps, some of which are printed upside down - tête-bêche.
'Upside down' was originally 'up so down', i.e. 'up as if down'. The 'so' part migrated into various forms, 'upsa', 'upse' (which spawned 'upset') etc., in the same way as in phrases like 'ups-a-daisy' and 'upset the applecart'. The change from 'up so down' to forms like 'upset-down' and eventually 'upside-down' appear to be for no better reason than to make the expression's meaning more intuitive.
'Upside down' doesn't sound especially old but, in its early forms, it can claim to be one of the oldest expressions in English. It joins the handful of phrases that can be dated from the first part of the 14th century or before, for example, 'haven't slept a wink', 'in the twinkling of an eye', 'by dint of'. The earliest version of 'upside down' known in print is in The proces of the seuyn [seven] sages. The precise publication date of that text isn't known, but it is accepted as being before 1340:
"The cradel and the child thai found Up so doun upon the ground."
See also: 'inside out'.