Desert island can be a confusing phrase. Most people probably assume that it can only be a hot, sandy place with a palm tree or two, an impression supported by countless New Yorker cartoons and TV commercials, conforming with the definition of desertplay as “arid land with usually sparse vegetation and hot temperatures.” We assume that the desert in desert island is the noun desert. In fact, the definition is simply "an island where no people live," so the desert in desert island is actually an archaic form of deserted: it refers to an island that is uninhabited, not one that is covered with sand (with the obligatory palm tree).
Desert and deserted share etymological roots from the Latin word desertus, which means “abandoned” or “deserted.” These English words date back to the 1200s, whereas the verb to desert, meaning “to abandon,” didn’t enter English until some 400 years later (with a detour through French). Therefore, although we might think of the essential qualities of a desert are sand and heat, the word truly refers to the lack of anything else, particularly people or cultivated land. Going back further into the word’s history, we see that desertus comes from de (“not”) + serere (“to join” or “to link together”)—it means “not joined” or “disconnected” from population and civilization and corresponds to the dictionary definition labeled archaic: “a wild uninhabited and uncultivated tract.” It’s obvious that the idea of the noun desert has blended with the adjective desert meaning “deserted” in the minds of most English speakers.
It’s clear in some early modern contexts that desert is used adjectivally to mean “uninhabited”:
The rest of the circumjacent islands are desert, or meanly inhabited by a few fishing people, but all of them stor’d with an abundance of Deer.
—Philosophical Transactions of the Royal Society of London, Volume 10, 1701
It’s also clear that desert island soon became a metaphor for “isolated place”; a play called The Desert Island was performed in London in the 1760s. This is a passage from its preface:
Your Bard to-night, bred in the ancient school, Designs and measures all by critic rule; ‘Mongst friends it goes no farther—He’s a fool. So very classic, so very dull, His Desert Island is his own dear skull.
—Pietro Bonaventura (translated by Arthur Murphy), The Desert Island, 1762
In the introduction to this play, the setting is described in terms that make it clear that this “Desert Island” is by no means arid and hot:
The Scene represents a Vale in the Desert Island, surrounded by Rocks, Caverns, Grottos, Flowering Shrubs, Exotic Trees, and Plants growing wild.
Indeed, the original Italian title of The Desert Island is L’Isola Dishabitata, which literally translates as “uninhabited island.” Daniel Defoe’s Robinson Crusoe has a chapter called “Wrecked on a Desert Island," a location that is clearly not a desert. Since there were native inhabitants in Defoe's novel, this use of the term, as well as the first quotation given in the Oxford English Dictionary, which refers to "many desart Islandes inhabited of wilde men," shows that "uninhabited" was used to mean "uninhabited by Europeans" for a long time.
There are other similar archaic forms of adjectives that are still used in specific instances in English: think of roast beef (instead of “roasted beef”).
The idea of a desert island as the perfect place to bring a record player and be alone with your favorite music (electricity worries notwithstanding) began in 1942, when the BBC began its show “Desert Island Discs” (the show is still running today). But even earlier, the idea that isolation provides a reason to choose one’s favorites was expressed in a quotation from 1930 in the OED: “I think I should choose it as my desert-island opera.”
The desertplay meaning “something deserved,” as in “They got their just deserts,” is an unrelated word that comes from the same French root as deserve. And dessertplay meaning “sweet food eaten after a meal” comes from the French verb desservir, which means “to unserve” or “to clear the table”—it’s what comes after the main plates are taken away.