What is the story behind the tall Northern offshoot on the West Virginia map?

The two key states in this drama were Virginia and Pennsylvania. The former, Virginia, initially claimed all of the land west of it all the way to the Mississippi River, with the Ohio River as its northern border. On the other hand, Pennsylvania, founded by the orderly and pacifist William Penn, defined itself as a rectangle (except where geographical features like the Delaware River in the east, and Lake Erie in the northwest prevailed), with the boundaries of 42 degrees to the north, 80 degrees 31 minutes to the west, and the Mason-Dixon line to the south.

After the founding of the United States, the 13 colonies were asked to limit their western claims to roughly the line of the Alleghany and Cumberland mountains to allow for the creation of new states to the west. This led to a partial "rollback" of Virginia's claims out of modern Kentucky, paving the way for the 15th state. When Ohio became the 17th state, it adopted the Pennsylvania border as its eastern boundary only as far south as the Ohio River, and the Ohio River itself as a "southern" boundary. This created the sliver of land between Pennsylvania's western boundary and the Ohio River (which veered to the southwest instead of due west) that was left in the hands of Virginia. Ohio may have done this in order to have a defensible border and avoid the fights the preceded the establishment of the Mason-Dixon line.

This realignment also began a debate as to whether Virginia should pull back further to (roughly) its current western borders, leaving room for the modern state of West Virginia. That debate was settled in June, 1861 at the Wheeling Convention, as "West Virginia's" response to the start of the Civil War, and Virginia's secession from the Union.

Panhandle Maryland

Look at that strange piece of Maryland between Pennsylvania and West Virginia… – @o0

I have also wondered about this while studying maps when younger.

On a visit in the later half of April 2013, driving from Kentucky to Maryland, we drove through this area.

One possible reason became clear: this was a valley where it would be difficult to cross over in the westernly direction when Maryland was formed in 1696.

The southern boundary was the Potomac River (just as the western boundary of West Virginia to Ohio is the Ohio river).

Only the northern boundary was an artificial, man made, boundary (which is also true for the eastern boundary between West Virginia and Pennsylvania).

Interstate 68
A road cut at Sideling Hill exposed geological features of the mountain and has become a tourist attraction.

• Sideling Hill Road Cut (I-68 and US 40, Maryland)

Sideling Hill Road Cut	Photographed from Interstate 70

When in Kentucky, I noticed a certain tree that had a reddish/purple colored leaves. I was told that this happened only for a few weeks in spring.

These trees, that intermingled with other 'normal' trees, could still be seen while driving through West Virginia. In Maryland they, however, 'disappeared'. My friend pointed out a tree with a more darkish colored green leaves and said that it was the same tree we saw before that had lost the reddish color.

It was, climate wise, as if one had traveled 2 weeks into the future. I found that very impressive.

Some colonies, including Virginia, claimed all land to their west. Other states, including Pennsylvania, had defined western boundaries:

Ever since the proprietary grant to William Penn in 1681, the border between Virginia and Pennsylvania had depended upon defining the eastern edge of Pennsylvania. Once that eastern edge of Pennsylvania was resolved, surveyors could locate a north-south line "five degrees in longitude, to bee computed from the said Easterne Bounds..." to mark the western edge of Pennslvania. Until then, land speculators in Pennsylvania chartered the Indiana Company, while Maryland speculators formed the Illinois and Wabash companies, and sought rights to the same lands being claimed by the Virginia-based Ohio Company. (source)

Here's a map showing the state of claims in 1755, with VA in brown and PA in yellow:

You'll note that the map isn't great. (Look how squat western PA is, because Lake Erie looks too far to the south.) Poor mapping gave states with unlimited western territories room to maneuver in making claims on western territory. Land to the west of PA's western border thus had the potential to be claimed by Virginia. Indian fighting and the Revolutionary War prevented the settling of the boundary dispute. All of this geographical ambiguity meant that settlers in this disputed area were confronted with dual local governments, one loyal to Pennsylvania and the other to Virginia:

. . . there were, west of the Alleghanies, not only two different sets of magistrates, with their subordinate officers, constables, assessors, and organized companies of militia, over the same people in the Monongahela valley, but within a few miles of each other had been established two different courts regularly (or irregularly) administering justice under the laws of two different governments. These conditions, with these Virginia Courts exercising judicial powers in the same territory with the courts of Pennsylvania, continued until August 2S, 1780. (source)

Upon peace with Britain, a final surveying trip was completed during 1784-1786. Having definitively set the southeastern corner of PA, the surveyors could then definitively set the western border of PA. But by then, the Land Ordinance of 1785 gave all territory north of the Ohio River to the federal government, which would sell the land in order to raise revenue and (eventually) form new states. So Virginia was left with the tiny sliver of land west of Pennsylvania and south of the Ohio River. And of course, West Virginia took control of the panhandle after the Wheeling Convention of 1861.