Logistics.

There was a single track of railroad available for each of the three main axes of advance, which was inadequate to supply the requirements of an advancing army of the sizes employed. Further, each of the rail lines was of a different gauge (width) than the standard German design, necessitating a laborious switchover process. In the early days of the war, railroad gangs were even sent ahead of the armored spearheads to begin their work.

Supplementing the rail line with the usage of roads by using both motorized transport and horse-drawn wagons was hampered by a sparse road network that was not suitable for all weather operations or heavy usage. Due to a lack of availability of German trucks, these machines were requisitioned from all over the territory they controlled. This resulted in an astonishing array of types of vehicles--hundreds of different makes and models that were unlikely to share spare parts or maintenance requirements.

Christian Wolmar argues that the German command knew of these problems prior to the initial invasion, and that the only solution to this problem was a rapid and sustained advance to try to knock the Soviets out of the war. Hitler's prediction that the "whole rotten structure will come crashing down" didn't prove correct.

Source: Engines of War, Christian Wolmar

There are two main reasons why a war with Russia was desirable at the time. Firstly, the war in the west was all but over. France was defeated and only Britain held out. This meant that Hitler was free to turn his attentions elsewhere as Britain could be finished off later. Secondly, the USA weren't in the war. As studies of Hitler's Ideology indicate, the Lebensraum principle really meant that Hitler didn't want all that much of Russia to use for his own devices. As such, a quick winnable war with Russia before the USA were provoked into joining the war was extremely desirable as it would mean that Germany could fight on one front at a time.

Was this a realistic prospect? At the start, the Soviet army was awful. The conduct of their war against Finland was exceptionally poor and they struggled to overcome that foe. The first few months of Operation Barbarossa showed this to be the case as well as the Germans rapidly progressed.

The failure of Operation Barbarossa, however, was down to three main reasons:

Firstly, Stalin was willing to sacrifice everything to not lose the war. Human costs were allowable. Hitler had underestimated that and expected the state to crumble as it had in World War One. When it didn't, it turned a quick winnable war into a very difficult one.

Secondly and Thirdly are both down to the question of supplies. The issue for any country invading Russia is that it is a very big place and keeping supply lines is extremely difficult. However, the speed of the initial German advance threatened to make this issue irrelevant. It presented Hitler with a crossroads: He could have chosen to go for Moscow, capture the auspices of the Russian state that remained there and cut the head of the Bolsheviks off, more or less forcing Stalin to try and recover the west from the Crimea or behind the Urals. The other option was, of course, what he chose which was to divert the attack on Moscow into trying to secure the Crimea and the oil there. While they were able to do that, by the time they could turn their attentions back on Moscow, the Russians had gotten organised and the weather had turned meaning that the Germans were left static. This meant that the Russians were able to reinforce, break the weakened centre of the Nazi thrust towards Moscow and turn them back.

TL;DR - The Germans prepared for and needed a quick war. Strategic errors meant they didn't get it

The panzer invasion extended too far from the fuel and ammo supply. The train tracks were vulnerable to sabotage, and in warm weather, roads turned to muck so no means of supply were available.

The number of troops and equipment were too small to occupy such a large area. Even if the objective was to hold and police the territory, there were not enough forces. The German forces were more of an expeditionary attack, with no chance of holding the territory permanently.

There were large numbers of Soviet forces and reserves drawn from the entire Soviet territory. Despite huge losses, the armies kept coming.

The difficulty with invasion of Russia is the successful use of the tactic of withdrawing strategic leadership, war production and other reserves to the interior, so that there is no decisive target west of the Urals.

I would answer your question about what they could have done differently with another question: Did the German leadership know that they would eventually fail in their assault on the Soviets? I believe they knew it would fail (but have no proof). I believe that they wanted to choose the time of the battle so that the battle happened while Germany was technologically strong and industrially advanced and the Soviets were less advanced. If they waited 20 years, the Soviets could have attacked and might have been successful. Through the 1930s the Soviets were sending propaganda and provocateurs to push for communist rebellion in Germany, so from the German leadership point of view, the war had already begun. The German leadership likely feared that the Bolsheviks would have ruled all of Europe.

However, there was also a lot of stupidity in the German leadership, which explains the invasion just as well.

Source: Geschichte der rheinische-westfalischen 126. Inf. Div. 1940-1945, Gerhart Lohse

http://www.ausmeinerzeit.de/

One of the big mistakes may have been that they did not choose to wait until spring of 1942 to invade.

The initial plan had been to initiate Operation Barbarossa in May of 1941, but the Mediterranean theatre delayed this. Italy had, with very little warning to its German allies, decided to invade Greece. The Greeks fought harder than expected, and soon the Italians were pushed back to Albania, where they started. The Germans had to take control of the situation, as an allies-aligned Greece would pose a significant threat to the Romanian oil-fields, Germany's only source of oil up until that point of the war.

This diversion may seem at first to be insignificant, but Germany had to conquer basically the entirety of the Balkans in the process of getting to Greece. This campaign, though relatively easy for the Germans, required them to allocate a vast number of occupying troops. The Greek campaign both reduced the numbers of the prospective Russian invasion force, and delayed its start.

This delay (of roughly five weeks) seemed insignificant to Hitler and the higher-ups of the Wehrmacht at the time. They under-estimated Russian fighting power, and over-estimated their logistical abilities. One of the key goals to achieve by winter was to capture Moscow. This is for several reasons. One reason was that it would be an important logistical staging ground for the next stage of the operation, which would have begun in the spring of 1942 and pushed the Soviets over the Urals. But another reason was largely infrastructural. Very few roads east of the capital extended north-south, and this fact would hamper soviet logistics greatly. Supplies and manpower would not have been able to be delegated effectively along the soviet side of the front. If we count on the German blitzkrieg strategy of puncturing through defenses and sweeping back, lateral movement is key in strengthening parts of the front that are most threatened. It was believed that if this ability would be taken away from the Russians, they would be simply torn apart.

Unfortunately, (or fortunately, really) the Germans never captured Moscow. By December of 1941, infantry divisions could see the Kremlin. But winter was really setting in, and the Germans were not equipped for a winter war.

The reason for this is both lack of proper knowledge concerning war in such harsh environments, but also hubris by the higher-ups, who had assumed that by winter, the army would have achieved its strategic objective and housed up for winter barracks. This wasn't the case, and many Germans were left ill-equipped for the cold. No great-coats had been given to the soldiers, and their boots shrunk to their feet and froze to them. Soldiers everywhere got frostbite, and even minor frostbite can render a soldier incapable of fighting. And all this is not to mention the equipment failures, lack of fuel that would work in the cold, etc.

It's at this point that one can really see just how important the five-week delay may have been in dictating the outcome of the eastern campaign. Starting that much earlier may have allowed the Germans an entire month more to capture Moscow and other important targets while the Russians were still on their heels. But as the winter set in, the Germans lost all their momentum and the Soviets were given enough time to take the initiative. Perhaps it isn't professional to deal in what ifs, but in this situation, the plausibility is particularly tempting.