Frege's Puzzle is a puzzle about the semantics of proper names, although the title is also sometimes applied to a related puzzle about indexicals. Frege introduced the puzzle at the beginning of his article "Über Sinn und Bedeutung" ("On Sense and Reference"), one of the most influential articles for Twentieth-Century analytic philosophers and philosophers of language.
Consider the following two sentences:
(1) Hesperus is Hesperus.
(2) Hesperus is Phosphorus.
We can begin by noting that each of these sentences is true, and that 'Hesperus' refers to the same object as 'Phosphorus' (the planet Venus). Nonetheless, (1) and (2) seem to differ in what Frege called cognitive value. One way of analyzing this notion is to say that a person could rationally believe (1) while denying (2). The problem, however, is that proper names are often taken to have no meaning beyond their reference (a view often associated with John Stuart Mill). But this seems to imply that if a person knows the meanings of the words in (1) and (2), he cannot rationally believe one and deny the other: (1) and (2) are synonymous.
New Theories of Reference and the Return of Frege's Puzzle
Frege's solution was definitive for much of the Twentieth Century. Only recently, with the rise of anti-descriptivist (and thus anti-Fregean) theories of reference, has Frege's Puzzle become a dominant problem in the philosophy of language. This trend began some time in the late 1960s and early 1970s, when such philosophers as Keith Donnellan, David Kaplan, Saul Kripke, Ruth Barcan Marcus, and Hilary Putnam began to entertain arguments against Frege's theory. Perhaps most influential in this regard is Kripke's book of lectures, Naming and Necessity. To some extent, the resulting new theories of reference mark a return to the Millian view of proper names, and thus invite the problem of Frege's puzzle anew.
In the last several decades, then, many philosophers of language have attempted to work out a solution to the puzzle within the confines of direct-reference theories of proper names. Some of these philosophers include Nathan Salmon (e.g. in Frege's Puzzle and Content, Cognition, and Communication), Howard Wettstein (e.g. in "Has Semantics Rested on a Mistake?"), Scott Soames, David Kaplan, John Perry (e.g. in Reference and Reflexivity), and Joseph Almog.