Why did God kill a man for picking up sticks on the Sabbath? Now while the sons of Israel were in the wilderness, they found a man gathering wood on the Sabbath day. Those who found him gathering wood brought him to Moses and Aaron and to all the congregation; and they put him in custody because it had not been declared what should be done to him. Then the Lord said to Moses, “The man shall surely be put to death; all the congregation shall stone him with stones outside the camp.” So all the congregation brought him outside the camp and stoned him to death with stones, just as the Lord had commanded Moses.  - Numbers 15: 32-36 (NASB)

Why did God order the execution (and a brutal execution, at that) of a person for picking up sticks on the Sabbath?  Surely what this man did was nothing worse than what Jesus' disciples did when they picked heads of grain on the Sabbath:

And it happened that He was passing through the grainfields on the Sabbath, and His disciples began to make their way along while picking the heads of grain. The Pharisees were saying to Him, “Look, why are they doing what is not lawful on the Sabbath?”
...
Jesus said to them, “The Sabbath was made for man, and not man for the Sabbath. - Mark 2:23-27

Such a harsh punishment doesn't seem necessary if the Sabbath truly was made for man, and not man for the Sabbath.
Also, how does this align with the justice of God?  God forbids the punishment of those who beat their slaves:

If a man strikes his male or female slave with a rod and he dies at his hand, he shall be punished. If, however, he survives a day or two, no vengeance shall be taken; for he is his property. - Exodus 21:20-21

... yet He requires those who pick up sticks on a certain day of the week to be executed in the most unimaginably painful and cruel way.  In our 21st century minds, it seems that justice would demand that the punishments for these two crimes be switched.  What was God's reason for having such an inverted justice system?
Sometimes, God's Punishment for Disobedience is Death.

This is a simple fact. The severity of the punishment often corresponds to the severity of the offense, so why was this offense so severe? The text doesn't say this explicitly, but if we assume that God could have sufficient justification for execution, then it's likely that he was knowingly and defiantly disobeying a command he knew.

God places a high value on community and example. He seems to want to protect the community by insisting that everyone be a good example and that individuals who would do things that would lead their neighbors astray should be removed from the community (typically, executed).
Is disobedience a severe enough offense to warrant execution? To God, the answer is sometimes yes. The majority of these instances are examples to the community so that the people would take God seriously when he gives them commands. 

God insisted that Israel be different from the nations around them and wanted them to do things the way he had prescribed. We are not told precisely why these details about his prescribed methods are important, only that obeying them is. Two of Aaron's sons are put to death for "offering strange fire" (Le 10:1). The priest Uzzah was killed (by God) for touching the Ark of the Covenant (2 Sa 6), even though he had good intentions of saving the ark from accident, he knew full well that touching the ark was something he was not permitted to do. Ananaias and Saphira were killed (by God) for lying. Is lying that bad or was it important to demonstrate to the early church that God is both powerful and serious?

Though God is willing to forgive people, and punitive death is not synonymous with eternal damnation, he insists that we understand that he is not to be trifled with. His patience with us might be great, but in the end, his wrath is just as great.

Example

You compare the situations in Numbers 15 and Mark 2.

One obvious difference I see between these two is that of the motivation of the people who are doing the work. The disciples are doing this because they have been about God's work and are hungry. The man in Numbers 15 is not described as such. Though the text doesn't say one way or the other, it might be reasonable to assume that because the punishment is severe, so was the offense. He surely knew that he was supposed to do all that work the day before. It would be reasonable to conclude that he must have had selfish motivations for doing what he was doing. Work was certainly permitted on the Sabbath if the motivation were correct. (Mt 12:11)