2061 is set 51 years after the events of 2010: Odyssey Two. At the end of that novel, the enigmatic aliens who built the Monolith had transformed the planet Jupiter into a mini-sun in order to aid the evolution of life on Jupiter's moon Europa. A message was sent to Earth referring to Jupiter's moons:
ALL THESE WORLDS ARE YOURS—EXCEPT EUROPAATTEMPT NO LANDING THERE.
The opening chapters of 2061 gradually explain the events that have taken place in the interim years. The new sun, dubbed 'Lucifer', has transformed the moons of the former Jupiter: Io has become a volcanic hellhole, Europa an ocean world shrouded by clouds, and Ganymede a temperate world that the human race is colonizing. Large-scale interplanetary travel is now commercially viable with muon-catalyzed fusion-powered spacecraft. But humanity is wary of sending spacecraft close to Europa despite its fascinating mysteries, including the appearance of a large mountain, dubbed 'Mount Zeus', on its surface. On Earth, a period of relative peace has evolved between the U.S., USSR and China, although a violent revolution has taken place in South Africa (now the United States of Southern Africa or USSA): the white population fled to Europe, taking most of the country's wealth with them and leaving the black population to rebuild the economy, which they did in a matter of weeks thanks to the country's diamond mines.
Most of the novel repeatedly switches between two apparently separate plotlines that gradually converge.
Dr. Heywood Floyd, the hero of 2010 , has suffered an accident and has become a permanent resident on an orbital space hospital. His grandson Chris works aboard the spacecraft Galaxy and has not seen his grandfather in years. At the age of 103, Floyd is chosen as one of several "celebrity guests" to travel aboard the privately owned spaceliner Universe for the first-ever human landing on the surface of Halley's Comet as it makes its periodic pass through the solar system. The craft lands on the comet and the crew explore its surface and its caves.
On Ganymede, Rolf van der Berg, a second-generation Afrikaner refugee, studies data on satellite surveys of Mount Zeus and forms an astonishing thesis about its nature. He communicates his discovery to his uncle Paul Kreuger, and he is invited to join the crew of the spacecraft Galaxy for its flyby of Europa. As Galaxy nears Europa, Rosie, a stewardess, attempts to single-handedly hijack Galaxy , forcing it to crash into Europa's ocean. Failing in her (unexplained) plan, she commits suicide, and the crew of Galaxy is now stranded on their floating spacecraft. Observing the burgeoning aquatic life forms of Europa, the crew pilots Galaxy to an island which they name Haven.
Universe is forced to abandon its exploration of Halley to rescue Galaxy . After siphoning water from Halley's vents to refuel, an idea conceived by Universe' s navigation officer and advanced by Floyd, Universe heads directly for Europa without returning to Earth first. During the flight to Europa, the celebrity guests discuss the mystery surrounding Dave Bowman and the monoliths, and whether they would be allowed to land on Europa to rescue Galaxy ’s crew. Floyd follows a suggestion that he simply try to call Bowman on the radio, and that night has a strange dream in which he sees a small monolith (referred to as a minilith) floating at the foot of his bed.
On Europa, Van der Berg and Chris Floyd take the shuttle William Tsung (nicknamed Bill Tee ) to study Mount Zeus. Near Mount Zeus, van der Berg relays the message "LUCY IS HERE" to his uncle Paul. It is revealed that Van der Berg's hypothesis, now proven true, was that Mount Zeus is one huge diamond, a remnant from the core of the exploded Jupiter. (The novel explicitly identifies the source for this idea, and for Van der Berg's code: a 1981 article in the journal Nature hypothesizing that the cores of Uranus and Neptune are diamonds the size of Earth; the article is subtitled "Diamonds in the Sky?" in reference to the Beatles' song "Lucy in the Sky with Diamonds".) The revelation about Mount Zeus explains how Van der Berg got onto Galaxy and why Rosie tried to hijack it: both the rulers of the USSA and the exiled Afrikaners are concerned about what might happen to the world diamond market if a vast mountain of diamond was discovered.
Travelling further, the two men find the wreck of the Chinese spacecraft Tsien (which had crashed on Europa in 2010 ), which has been completely stripped of its metals, and then find the enormous, 3 km (1.9 mi) long monolith lying on its side at the border between the dayside and nightside, dubbed the "Great Wall". Beneath it is a town of igloo-like dwellings, but the inhabitants are not in sight. There, Chris sees an image of his grandfather, who appears to Chris in the same way that Bowman appeared to Floyd in 2010 , and tells him that the Universe craft is coming.
Universe rescues Galaxy' s crew; they are brought to Ganymede, where they watch as Mount Zeus, which has been steadily sinking, finally disappears beneath the Europan surface. Kreuger writes a follow-up article for Nature , stating that Mount Zeus was a mere fragment of Jupiter's core and it is almost certain that many more such large pieces of diamond are currently in orbit around Lucifer. He proposes that a program be initiated immediately to collect these enormous quantities of diamond and put them to use.
Floyd and Chris become close again, and both become friends with van der Berg. They talk about how Floyd called Bowman on the radio, and Chris asks if Bowman ever replied. Floyd almost tells his grandson about the minilith in his cabin, but does not after rationalising that it was probably a dream. However, Floyd is wrong. In a later chapter, another Heywood Floyd, now a disembodied creature of pure consciousness, talks with Dave Bowman. It is revealed that the minilith duplicated Floyd's consciousness; there are now two Heywood Floyds, one an immortal being who resides with Bowman and HAL inside the Great Wall, another who will live and die without knowing this. Bowman shows Floyd images of his experience of studying the life forms of Jupiter before they were killed in the creation of Lucifer, explaining that the monolith weighed the Jovians against the Europans and decided the latter held more promise. Bowman and HAL believe that when Lucifer begins to fail, the monolith will weigh the Europans against humanity, and they have only about a thousand years to prepare for that moment.
In an epilogue, set in the year 3001, the original monolith discovered on the moon in 1999 has been placed in the plaza of the ancient United Nations Building. Humans have found more quantities of diamond from the former Jupiter and have used it to create space elevators and an orbital ring connecting them, as suggested by Kreuger. (This idea will later be a central concept in 3001: The Final Odyssey .) Suddenly, Lucifer's light begins to fade, and the Monolith awakes.