The short answer is yes, the Nazis made some attempts to hide what they were doing from the public eye, but anyone who wanted to know what was happening could figure it out pretty easily, and it was something of an "open secret" in wartime Germany. The German people had heard Hitler's antisemitic, exterminationist rhetoric for years, and despite the Nazis' efforts to conceal their actions through censorship and carrying out most of the killing well away from the (German) public eye, word-of-mouth got around, and even if it didn't, any reasonably intelligent person could put the two-and-two together if they wanted to.

Before the "Final Solution to the Jewish Question" began, the Nazis had already carried out one program of mass murder: the Aktion T4 "euthanasia" program (which lasted from 1939 to 1945, but was most concentrated in 1940-1941), in which psychiatric patients and other people with mental and physical disabilities were murdered. These killings used the same methods that would later be used at the extermination camps: the victims were killed by asphyxiation in gas chambers (generally using carbon monoxide gas) and then cremated. Again, to anyone who wanted to know, it was very obvious what was going on. Buses went to the killing facilities loaded with people and left empty; thick, acrid smoke came from the chimneys and spread across the surrounding towns on a regular basis. Not in any way subtle. The T4 program prompted a public outcry, particularly from Catholic groups, which caused the Nazis to shut the program down, at least officially, in 1941 (although the killings actually continued until the end of the war).

In many ways, the T4 program was a "trial run" of the Final Solution. Not only were the killing methods similar, many of the personnel involved in T4 later went to Poland to implement the gassing facilities and serve as commanders at the extermination camps. It's notable that all of the extermination camps were located outside of the prewar borders of Germany (Auschwitz and Chelmno were in territories annexed by Germany, but both areas had been in Poland prior to 1939). Part of the reason for this was that their largest task was the extermination of Polish Jews (more than 3,000,000 people), and the geographical proximity to major rail lines in Poland was practical. But it also helped to keep the mass murder of the Jews out of the (German) public eye, since it wasn't occurring in German towns, like the T4 program had. The Nazis learned their lesson in that respect. They also opted for different gassing methods, generally using either Zyklon B (a cyanide-based pesticide) or exhaust from an engine, rather than bottled carbon monoxide, both because bottled CO was expensive and because the shipment of such large quantities of CO would immediately raise red flags.

That said, it was very obvious to the people in the surrounding areas in Poland what was going on. Again, large trains full of people went to these camps and came back empty, and the crematoria produced heavy, acrid smoke that people could smell for miles around. As the interviews in Claude Lanzmann's documentary Shoah demonstrate, the local Polish people were aware of what was going on and for the most part simply adapted to it, resigned to the conclusion that there was nothing they could do. One of the things that stuck with me most from that documentary was a Polish farmer who lived near Treblinka who said "you really can get used to anything."

People living in Germany didn't have the same kind of direct evidence that people living in the vicinity of the extermination camps did, but there were enough rumors passed around that anyone who wanted to know, knew; the authorities could censor mail, but word-of-mouth still made its way around. Ian Kershaw has shown that Germans living further east had a greater awareness of the extermination of the Jews than those further west, simply because they were in closer proximity to the extermination camps, demonstrating the power of both direct witnesses and word-of-mouth. Germans also knew about the regular concentration camps (those operated by the SS-WVHA, as opposed to the extermination camps operated by the SS-TV), many of which (e.g. Dachau and Neuengamme), were located in or near major cities, and they were aware that the prisoners there were treated badly and that prisoners died in those camps.

Kershaw's research also showed that most Germans could have figured out the implications of the deportations of German Jews, which almost everyone was aware of. He and others have stated that the public may not have been aware of the exact process (i.e. that the deported Jews were being gassed in purpose-built facilities), but they were aware in general terms of what was going to happen to the deportees. Interviews with ordinary Germans that were conducted many years after the war demonstrated that a substantial proportion either knew or suspected what was going on, despite the general tendency in the immediate aftermath of the war for people to plead ignorance. If you want to read a collection of such interviews, I would suggest Eric Johnson [disclosure: he was my doctoral advisor] and Karl-Heinz Reuband's book What We Knew, in which they conducted a large-scale survey of German people who had lived through the Nazi era about their knowledge of Nazi crimes.

The public awareness of the "Holocaust by bullets" carried out by the Einsatzgruppen, Wehrmacht, and German and local auxiliary police forces in the occupied Soviet Union was probably lower. As you noted, mail from the Eastern Front was heavily censored, and any mention of mass killings would have likely been redacted. However, soldiers still came home from the front, and despite official prohibitions, they told people what was going on, and that word got around too. Kershaw noted that people who traveled to the east for work also encountered witnesses to the mass killings there (many of the locals were fully aware of the massacres due to their sheer scale), and were able to bring that information back to Germany. In addition, there were a few cases where evidence sent from the Eastern Front was intercepted prior to being confiscated by German censors; a famous example is the "Ivanhorod Einsatzgruppen Photograph", which was intercepted by the Polish Underground at a postal facility in Warsaw and relayed to the government-in-exile in London (although it wasn't published until after the war).

So to conclude, yes, the Nazis tried to hide the Holocaust, but for the most part, if people didn't know, it was because they didn't want to know. The combination of the Nazis' own statements and policies, the evidence of deportation in front of their eyes, and the substantial amount of rumors and reports that made their way westward through Germany meant that almost anyone could have figured out or found out what was happening to the Jews.

Sources:

I mainly drew on Ian Kershaw's Hitler, the Germans, and the Final Solution (Yale UP, 2008), which is excellent and I highly recommend it if you're interested in the topic.

If you read German, you might also check out Frank Bajohr and Dieter Pohl, Der Holocaust als offenes Geheimnis: die Deutschen, die NS-Führung und die Alliierten (Beck, 2006) [The Holocaust as an Open Secret: The Germans, the Nazi Leadership, and the Allies].