You are actually referring to the 1977 deaths of Gudrun Ensslin, Jan-Carl Raspe, and Andreas Baader on "Death Night" in Stuttgart's Stammheim Prison (not 1976, though their comrade Ulrike Meinhof did commit suicide in the same prison block in 1976.

The preponderance of the evidence makes it clear that the most likely explanation is that they committed suicide, though there is so much weirdness associated with the events that it is entirely understandable to question the official verdict.

Context

Throughout the 1970s the Red Army Faction (popularly known as the Baader-Meinhof Group or Baader-Meinhof Gang) waged "war" on West Germany and the United States, in an attempt to kickstart Revolution and inspire others into ushering out Late-Stage Capitalism and usher a Socialist society.

They were effectively founded in May of 1970 when famous journalist Ulrike Meinhof helped break convicted arsonist Andreas Baader from police custody. For the next two years their ranks grew to as many as 100 young Germans; as they robbed banks and plotted their war. In May of 1972 they began a bombing campaign across Germany that killed four US servicemen, and maimed dozens of Germans and Americans. In rapid succession the entire leadership of the group was captured, though many lower-lever members remained on the run.

Over the next five or so years, the remaining members of the group changed their general goal of Revolution to a more immediate goal of securing the release of their imprisoned leaders from Prison. While this was going on, the German government was gearing up for what would prove to be the largest and most expensive trial in West German history.

Because of very legitimate concerns about rescue attempts during the trial, the government built a special courthouse right on the property of Stuttgart's Stammheim Prison. They also established a special prison block at the top of the prison for the exclusive use of the prisoners; they were not allowed to interact with the other prisoners in the facilty.

The prison block was described as the "most secure prison block in the world." Lawyers and other visitors were subjected intensive searches that at times took up a full hour or more.

During this time, member of the RAF outside of the prison engaged in kidnappings, murders, and hostage taking in an attempt to secure the release of the leadership; all to no avail. On particular deadly attempt was their takeover of the West German embassy in Stockholm in 1975, when the member of the RAF murdered two diplomats and were prepared to murder more, one every hour, until one of the RAF members accidentally set off their bomb cache, maiming almost everyone inside (he later died from his injuries).

In 1976 the two-year long trial finally came to a conclusion with guilty verdicts for all of the defendants. In the ensuing year the prison block continued to house most of the leadership, while other members of the group were cycled in and out as well as the West German government decided where each prisoner would ultimately serve out their sentences.

In September of 1977, members of the RAF kidnapped Hanns-Martin Schleyer, a very prominent industrialist associated with the auto manufacturing industry (also, like so many prominent business and government leaders, a former Nazi). He was held hostage while his kidnappers would release videotapes to the press of him asking for the release of the prisoners in exchange for his life.

After a month of tension, the RAF worked with the People's Front for the Liberation of Palestine to hijack a German airliner. The plane was diverted all over the middle east, while German government officials tried to negotiate with the terrorists, who demanded the release of the RAF leadership, among other imprisoned terrorists. They also secretly activated their anti-terror squad, the GSG-9, who flew into mogadishu under the cover of darkness, and eventually raided the German airliner, rescuing all of the hostages.

Early the next morning, as all of West Germany breathed a collective sigh of relief that their countrymen and women had been rescued, they also learned of the almost incomprehensible deaths of three of the RAF leaders in prison (along with another leader, who barely survived being stabbed in her chest.

The Official Story

At the time, the official story seemed incredible. Two of the prisoners, Baader and Raspe, died from gunshots from two DIFFERENT guns that had supposedly be smuggled in. Irmgard Moeller had supposedly stabbed herself, with a smuggled butter knife, so deeply in her chest that it almost pierced her heart.

And they coordinated their actions when there was supposed to be no way to communicate between cells, and no way of learning about the the rescue of their airline hostages.

It just seemed insane.

But what emerged in the days, months, and years later would eventually show that the official scenario was the most likely scenario.

It emerged that while lawyers were routinely searched for up to an hour when visiting the prisoners, during the trial when the lawyers interacted with the defendants, few security measured were employed. This allowed confederate lawyers to pass notebooks, ostensibly filled with case documents but actually containing hidden weapon, to the defendants. During this time the prisoners were enlisted to help with some renovations of the cell blocks, allowing them to build in secret an essentially undetectable hiding spaces in their walls.

The prisoners also employed a fair genius communication system; using speakers and coils from their record players, as well as spare batteries, they were able to rig up a rudimentary "phone" system between the cells, using the electrical wiring between cells (which was turned off at night) as a conduit. Though they were not allowed radios at this point, one of the group members actually WAS able to hide a smuggled transistor radio.

Beyond all of this, it is really important to look at things from the prisoner's perspective. They had been waging this "war" for 7 years now. Yet every milepost of the last 4-5 years was a defeat. Numerous attempts to free them had failed, they had lost their trial, and the latest one-two punch of the kidnapping of Schleyer and the airline hijacking had ended in defeat. And soon they would all be split up in prisons around the country. A joint and "suspicious" suicide could be viewed as their one final "attack" on the state... an event that would leave everyone with even a smidge of sympathy for them to assume that the government had murdered them.

In fact in the months leading up to their deaths, leaders of the group conveyed a message to their followers on the outside (through a mid-level member who had just been released from prison): "If you hear that we "commit suicide" in prison, don't believe it; even if we do the act ourselves, it was the state that killed us" (or words to that effect).

Eventually one (maybe two?) of the former lawyers of the group were convicted of smuggling in the guns.

But as I alluded to above, there is much weirdness:

There was a guard not more than 20 feet away from the cells of of Baader, and Raspe. How did he not hear gunfire?

Baader was shot in the head, TWICE.

I still don't have a good answer for the first point; though it IS important to note that the members of the RAF were noted for having members research their guards' lives, and then quietly walk up to a guard and say something to the effect of "hey, your wife and three children living at 1234 Bergenstrasse, in Ulm sure would hate to be kidnapped themselves, or simply turn up missing." Though I have no particular facts to back up any supposition about the gunshots not being heard, I could imagine scenarios where either the guard was asleep and was embarrassed, or DID hear the shots but was too scared to do anything.

Who knows. But it doesn't particularly feel like some kind of proof that they were murdered.

In terms of Baader getting shot twice; the first bullet just grazed his head and the second one was fatal; it's not like trying to kill yourself isn't stressful enough; it's easy enough to imagine doing a bad job of pointing when holding a gun to the back of your own head... and then doing it "right" the second time.

Moeller, the woman who apparently stabbed herself with a bread knife, has always claimed she was attacked by guards; a claim she has never wavered from (she spent another 20 years in prison before getting released in the late 90s).

Aftermath

Pretty much instantly after the deaths were revealed it become an assumption on the left to assume they were murdered by the state, and an assumption on the right to assume they committed suicide. This dividing line has lessened over the years; partially due to the supporting evidence for the suicide scenario.

Bonus:

This is one of my favorite pieces of art of all time; Norwegian Artist Odd Nerdrum, in full Caravaggio-mode, imagines the death of Baader as a 1930s Dashiell Hammett murder:

http://i.imgur.com/WyWfw.jpg

Additional Reading:

Aust, Stefan. "The Baader-Meinhof Complex"