Southern territory, concluding with Sherman's frenzied advance into subjugating the South.

Contrast the repeatedly poor military leadership of the Union armies in the early years of the war (Scott, McClellan) with the consistently excellent leadership of the Confederate armies (Lee, Stuart, Longstreet, Forrest) and you get another angle on the answer.  The North had almost every advantage, but the South had a long standing military tradition, and a lot of the best and brightest West Point graduates in their ranks.  They fought a brilliant defensive war and inflicted greater casualties on their enemy.

In the end, a few key Confederate mistakes (Gettysburg among them) and a long, painful process of bludgeoning the southern armies into submission was the path the Union followed to a very costly, bloody victory.

There are several reasons that it took the Union so long to win this war.  At first, it looked as though the Union had all the advantages and this would be a short war. First, the Union had the large population, people to fight in the war and work in the factories to make war materials.  The North also had the industrial base, the factories to make these war materials.  The Union also was wealthier than the Confederacy and could finance the war.  The Union had an established army and government, but the Confederacy would have to build their army and government from scratch.  Finally, the Union had a navy which they used to blockade the southern coast. But the Confederacy had advantages, too.  The Confederacy would be fighting a defensive war, which is much easier than having to invade and conquer a territory, something the Union would have to do. Because the Union would have to invade the south, their supply lines would be much longer, and the Confederate army’s supply lines would be much shorter.  Because they would be fighting on their own land, they could take advantage militarily of their knowledge of the land.  They would be defending their homeland which would give them a strong incentive to fight.  They would also be fighting among friendly people. Finally, some of the best military leaders, such as Robert E. Lee and Thomas “Stonewall” Jackson, chose to fight on the side of the Confederacy.  It took Lincoln almost three years to find a competent commander in Ulysses S. Grant.  It was because of these Confederate advantages that the war took so long for the Union to win.

One of the other difficulties faced by the Union, particularly early in the war, was apparently rather conservative and hesitant leaders both in the field and back at home.  Generals were skittish about big defeats, particularly once they learned that the Confederate Army was actually rather good at the type of fighting required, and so tended to sit back and try to let others take the initiative.

The Union in some ways was also at a disadvantage because they needed to bring the war to the Confederates, and particularly in several battles they were forced to attack fortified positions leading to huge numbers of casualties and further political pressure to get it right.

There is no one simple answer to this.  My take on it is that the Union took so long because it had a very difficult job to do in order to defeat the Confederacy.

If you think of the way the war went, the Union had to penetrate deep into Confederate territory (who knows what would have happened if McClellan had done better with his Penninsular Campaign, though).  The really important campaign was one that went through places like Chattanooga and Atlanta -- very far from Union territory.

So even though the Union had all sorts of material advantages, it had to get its soldiers all the way into Confederate territory and solve all the military problems that come with having long, exterior supply lines.  This, to me, is why they had so much trouble.