Warning: Wikipedia contains spoilers
Doug Quail, a simple and ordinary man, wishes to visit Mars. Unable to afford it he visits a company, Rekall, that offers implanted memories ("extra factual memory"). The attempt to implant some racy Mars memories of Quail as a secret agent reveals that Quail actually is an undercover government assassin with a mind full of dangerous secrets. The Rekall staff quickly get Quail out of there; he heads home and finds certain physical evidence to support his new old memories. The government initially seeks his death but instead Quail manages to make a deal. He returns to Rekall to have his Mars memories once more suppressed, and is offered by way of compensation a set of heroic wish-fulfillment false memories. The Rekall staff begin the memory-implanting procedure - and uncover a different and older set of suppressed memories revealing that the unbelievable memories they are about to insert are already there and are true.
The plot was the inspiration for the 1990 science fiction film Total Recall, starring Arnold Schwarzenegger. In the film the hero, renamed Quaid, actually travels to Mars, but the initial memory implant scene foreshadows much of what he achieves - kills the bad guys, gets the girl, saves the planet.