Adam Smith used the comparison of diamonds and water to make a distinction between what he called "value in use" and "value in exchange." The quotations here taken from the version of the Wealth of Nations that is freely available on-line at the Library of Economics and Liberty website. Smith wrote:
"The word VALUE, it is to be observed, has two different meanings, and sometimes expresses the utility of some particular object, and sometimes the power of purchasing other goods which the possession of that object conveys. The one may be called 'value in use ;' the other, 'value in exchange.' The things which have the greatest value in use have frequently little or no value in exchange; and on the contrary, those which have the greatest value in exchange have frequently little or no value in use. Nothing is more useful than water: but it will purchase scarce any thing; scarce any thing can be had in exchange for it. A diamond, on the contrary, has scarce any value in use; but a very great quantity of other goods may frequently be had in exchange for it."
In the classroom, the example is often then used to make two conceptual points. One is that economics is about value-in-exchange, and that value-in-use is a fuzzy concept that Smith (and the class) can set aside. The other is to explain the importance of scarcity and marginal analysis. Diamonds are high-priced because the demand is high relative to the limited quantity available. Water is inexpensive because it is typically fairly abundant, but if one is dying of thirst, then it would have a much higher value-in-exchange--conceivably even greater than diamonds.
It now seems possible that Uranus and Neptune may have oceans of liquid carbon, with diamond icebergs floating in them. (For a readable overview, see here. For an underlying scientific paper, see J. H. Eggert et al. 2010. "Melting temperature of diamond at ultrahigh pressure." Nature Physics 6, pp. 40-43.) On such planets, the scarcity and price of water and diamonds might well be reversed!
But at a deeper level, Michael V. White pointed out 10 years ago in an article in an article in the History of Political Economy that Smith wasn't thinking of this as a "paradox" ("Doctoring Adam Smith: The Fable of the Diamonds and Water Paradox," 2002, 34:4, pp. 659-683). White traces the references to the value and price of diamonds and water through Jeremy Bentham, David Ricardo, William Stanley Jevons, Alfred Marshall, and other luminaries. In various ways, these writers all deconstructed Smith's paragraph to argue that value could not depend on use alone, that "use" would vary according to scarcity, that supply must be included, and so on.
Of course, Smith was aware of the importance of scarcity. A few chapters later in the Wealth of Nations, he revisited the subject of the price and value of diamonds in several other passages. He wrote:
"Their highest price, however, seems not to be necessarily determined by any thing but the actual scarcity or plenty of those metals themselves. It is not determined by that of any other commodity, in the same manner as the price of coals is by that of wood, beyond which no scarcity can ever raise it. Increase the scarcity of gold to a certain degree, and the smallest bit of it may become more precious than a diamond, and exchange for a greater quantity of other goods. ...The demand for the precious stones arises altogether from their beauty. They are of no use, but as ornaments; and the merit of their beauty is greatly enhanced by their scarcity, or by the difficulty and expence of getting them from the mine."
"Smith's `failure' to correctly analyze utility was attributed to his personality, which, Douglas asserted, reflected a national stereotype. The inability to follow the `hints' of his predecesssors (Locke, Law, and Harris) was due to Smith's `moralistic sense. ... in his thrifty Scottish manner with it sopposition to ostentation as almost sinful he concluded that diamonds 'have scarce any value in use.' The stingy Scot had thus managed to `divert' English (!) political economists `into a cul-de-sac from which they did not emerge ... for nearly a century. Smith on value and distribution was embarrassing: `it might seem to be the path of wisdom to pass these topics by in discreet silence.'"
Paul Samuelson was a student of Paul Douglas at the University of Chicago, and Samuelson inserted the diamond-water question into his 1948 textbook, where it has remained a standard example--and for all the ambiguity and complexity, I think a useful piece of pedagogy--since then.