(covers information from several alternate timelines)
The Kobayashi Maru scenario was an infamous no-win scenario that was part of the curriculum for command-track cadets at Starfleet Academy in the 23rd century. It was primarily used to assess a cadet's discipline, character and command capabilities when facing an impossible situation, as there is no (legitimate) strategy that will result in a successful outcome.
The test primarily consisted of the cadet placed in command of a starship. The ship would soon receive a distress signal from the Kobayashi Maru, a civilian freighter within the Klingon Neutral Zone that had been heavily disabled. Being the only ship in range, the cadet usually either chose to withdraw from the rescue mission or enter the neutral zone and rescue the vessel in risk of violating the treaties. The ship would then be confronted by Klingon K't'inga-class battle cruisers, which typically engaged in a firefight.
It was considered an absolute no-win scenario because it was virtually impossible for the cadet to simultaneously save the Kobayashi Maru, avoid a fight with the Klingons and escape from the neutral zone with the starship intact. A cadet's choice of how to handle the rescue operation gave great insight into his or her command decision-making.
In the 2250s, James T. Kirk became the first (and only known) cadet to ever beat the no-win scenario. After taking the test and failing twice, Kirk took the test a third time after surreptitiously reprogramming the computer to make it possible to win the scenario.
Kirk was subsequently awarded a commendation for "original thinking" and later commented, wistfully, that his stunt "had the virtue of never having been tried." Although Kirk understood that the purpose of the scenario was to confront cadets with a type of situation that they might encounter on duty, he defended his "cheating" by maintaining that he did not believe in no-win scenarios.
In March of 2285, Kirk, then an admiral serving as an instructor at the Academy, supervised Lieutenant Saavik's performance in the Kobayashi Maru scenario. Former Enterprise crew members Spock, Sulu, Uhura and McCoy participated as "actors" in the simulation. In the simulated bridge, Saavik was placed in command of the USS Enterprise on a training mission to Gamma Hydra near the Klingon Neutral Zone. The starship received the distress call from the Kobayashi Maru, disabled after having struck a gravitic mine.
Saavik chose to pursue a rescue and enter the neutral zone, quickly alerting three Klingon K't'inga-class cruisers. The enemy ships fired at them causing several bridge consoles to explode, "killing off" various officers and Saavik ordered all remaining hands to evacuate. Saavik's performance was considered "predictably dismal"; as Kirk observed to Spock, "[She] destroyed the simulator room and you with it."
After the Battle of the Mutara Nebula, Spock admitted he had never taken the Kobayashi Maru test, but before he died of radiation poisoning, he described his sacrifice to save the Enterprise as his "solution" to the scenario. (Star Trek II: The Wrath of Khan)
While breaking Leonard McCoy out of a Federation prison and plotting to steal the Enterprise from the Spacedock in Earth orbit, Admiral Kirk contacted Commander Chekov with the coded message "The Kobayashi Maru has set sail for the promised land." (Star Trek III: The Search for Spock)
By 2293, the term "Kobayashi Maru" had became a slang term for any hopeless or seemingly impossible situation, at least in Starfleet culture. Leonard McCoy considered his and James T. Kirk's imprisonment on Rura Penthe to be a "Kobayashi Maru" and told Kirk as much, on their first night at the penal mine. (Star Trek VI: The Undiscovered Country)
Commander William T. Riker mentioned that his classmate Paul Rice had beaten a difficult Starfleet Academy test by disregarding three options and coming up with a 4th option which worked. (TNG: "The Arsenal of Freedom")
In 2370, Deanna Troi questioned whether the final part of the Bridge Officer's Test was a no-win scenario, recalling simulations similar to the Kobayashi Maru. However, she discovered her test did have a solution, requiring ordering a subordinate to his death. (TNG: "Thine Own Self")
In 2379, Data faced with a no win Kobayashi Maru scenario, sacrificed himself to save the many similar to how Spock had sacrificed himself to save the many. (Star Trek Nemesis, Star Trek II: The Wrath of Khan)
A similar simulation was later used in the 24th century. It involved a damaged Ferengi ship as well as Romulan D'deridex-class Warbirds, instead of a civilian freighter and Klingon battle cruisers, and was performed on the holodeck. However, according to Tuvok this version did have a correct solution, that being to retreat. (VOY: "Learning Curve")
In the alternate reality, the Kobayashi Maru test was programmed by Spock between 2254 and 2258. Its purpose was to cause the cadets to "experience fear in the face of certain death" and learn to remain in control of themselves and their ship, despite that fear. Unlike the simulation in the prime reality, Starfleet Command this time specifically ordered the USS Trainer to rescue the USS Kobayashi Maru from a fleet of attacking Klingon warbirds.
In 2258, James T. Kirk, on his third attempt at the scenario, inserted a subroutine to make it winnable by eliminating the attacking Klingon vessels' shields and rendering them vulnerable to a single photon torpedo strike. Unlike in the prime reality, Kirk's behavior was considered unacceptable to his superiors, and he was brought up on disciplinary charges in a formal assembly of Starfleet personnel. The hearing was interrupted by a distress call from Vulcan, which was under attack by the time-displaced Nero, and Kirk was placed on academic suspension, until the Academy Council could rule on his case. The outcome of the hearing is never directly stated, but as he gets promoted and continues to serve in Starfleet, the Admirality seems to have dropped the charges, probably due to his heroic actions on board the Enterprise. (Star Trek)
The earliest version of the Kobayashi Maru scenario was in a script draft that Jack B. Sowards wrote for Star Trek II. In this document, the simulation was much as it is in the film's final version, involving the attempted rescue of the Kobayashi Maru and Kirk suggesting that the test might be a "no win scenario." (Star Trek: The Magazine Volume 3, Issue 5; ) Sowards named the scenario for some former neighbors of his. 
Depicting the origin of the Kobayashi Maru test was one of multiple plot concepts that the writing staff of Star Trek: Enterprise suggested to Brannon Braga in a memo full of "story ideas" (the memo was dated 24 April 2001). It was proposed as a one-line pitch, though the memo also included more extensively written narrative suggestions. However, the Kobayashi Maru idea wasn't produced, unlike some of the other ideas.
In the audio commentary for the film Star Trek, writer and producer Roberto Orci states that he imagined that Spock also programmed the test in the prime reality, and that Kirk met him the same way after cheating.
The Kobayashi Maru scenario has also appeared in novels, short stories, video games and comic books.
The origin of the Kobayashi Maru scenario was revealed in Michael A. Martin and Andy Mangels' Star Trek: Enterprise novel Kobayashi Maru set in 2155. In it, the Kobayashi Maru – here a freighter carrying secret Starfleet equipment to set up a listening post near the soon-to-be-established Neutral Zone – was hit by a gravitic mine in the Gamma Hydra Sector. When Enterprise came to save the Kobayashi Maru, the Romulans attempted to use a telecapture device on Enterprise – thus allowing them to take control of the ship by remote – and bring in three D-5 class Klingon battle cruisers to ensure the elimination or capture of Enterprise.
Jonathan Archer was faced with the decision of losing his ship and the survivors or sacrificing the survivors and ensuring the survival of Enterprise, thus the no-win scenario, as Archer had been told to protect the freighter at all costs. Systems begin to fail on Enterprise indicating the ship was about to be taken over and Archer reluctantly chose to retreat.
Julia Ecklar's The Kobayashi Maru tells how Kirk, Pavel Chekov, Montgomery Scott and Sulu each faced the problem. In the novel, Kirk won the scenario by reprogramming the simulation so that the Klingons believed he was a famous starship captain, though he was only a cadet at the time. Chekov self-destructed his ship, taking the Klingons with him; to his humiliation, his instructor pointed out that ejecting his crew in lifepods did not save them, due to the explosions of the four warp-drive vessels and the attending radiation.
Scott tricked the simulation into overestimating the effectiveness of a theoretical attack against the Klingon ships' overlapping shielding. Faced with proof that such attacks, although quite valid in theory, would not work in reality and that Scott knew this, Academy staff reassigned Scott from command school to Engineering (his true love – he had used this "solution" precisely because of these consequences). Sulu, given the consequences of entry into the Zone versus the slim chance of recovering the crew of the freighter, elected not to conduct a rescue operation.
Diane Carey's Dreadnought! shows Piper almost beating the test by using a hand communicator to effectively hack the computer and make the simulation fight itself, nearly crashing every operating system in the Academy.
The Star Trek: Starfleet Academy game provides the test as one of the missions in the game scenario. Imitating Kirk, the player character has the choice to reprogram the simulator and win the mission. One of the options is to make the AI-Klingons believe that the cadet protagonist is a famous captain and obey him at once. The other two options -- making the Klingon ships weaker or dumbing down their AI -- will permit the player to defeat the Klingons but cause the program to crash, implying that Kirk chose the option to make the Klingons fear and respect him.
In Peter David's Pocket TNG novel A Rock and a Hard Place, Jean-Luc Picard has some misgivings about accepting a maverick officer as Will Riker's temporary replacement, but is astounded to be told that said officer beat the Kobayashi Maru without cheating (according to the admiral telling Picard this, "programmers were in mourning for a week.")
In the short story "'Til Death", part of the The Sky's the Limit anthology it's stated that when Will Riker took the Kobayashi Maru, he ordered an EVA suit brought to the bridge so that he could fight the enemy ships by hand. This gambit did not appear to have been successful.
In Peter David's New Frontier novel Stone and Anvil, cadet Mackenzie Calhoun "wins" the scenario by destroying the freighter, disabling the attacking ships in the process, escaping with his ship and crew but killing those whom he had been attempting to rescue (he later defended his actions by claiming the scenario was clearly a trap and the freighter crew were most likely already dead – and if they were alive, this quick death was preferable to the treatment they would receive as prisoners. And the whole thing probably is a trap; the Kobayashi Maru is probably an enemy ship). By this time, the scenario had been upgraded with holodeck technology, enabling variations on the basic theme of a starship in trouble.
In the novel Sarek by A.C. Crispin, Peter Kirk beats the scenario by using a knowledge of Romulan customs unanticipated by the test's designers, challenging their captain to ritual combat – since all other hostilities must cease during the duel, the Romulan ships can only watch as Kirk's ship rescues the Kobayashi Maru crew and escapes unharmed.
In "The Bottom Line" by Andrew Morby (SNW III) and Shawn Michael Scott's "Best Tools Available" (SNW VI), Cadet Nog solves it in two entirely different (and thoroughly Ferengi) ways. In one case, he lures the enemy onto his ship, which he has set to self destruct but with the announcement volume so low only he can hear it. In the other, when the simulated Romulan commander tries to demand his surrender, Nog replies "Name Your Price", and proceeds to haggle until the simulation crashes, as the programmers had never considered this possibility.
Kevin Lauderdale's "A Test of Character" (SNW VII) depicts a different solution from Ecklar's, one in which Kirk's tampering is "cheating without cheating," since Kirk merely creates a level playing-field, where success is not guaranteed.
Star Trek Online features a Kobayashi Maru-inspired mission wherein the objective is to defend a civilian transport from an increasingly difficult onslaught of enemy ships. The accolades (achievements in STO) for completing high-level waves directly reference James Kirk. The mission, appropriately enough, is called "No Win Scenario".