Q:

"Barking up the wrong tree" <- What does "bark" refer to here?

In the well-known idiom to bark up the wrong tree, what is the underlying metaphor? In particular what is the meaning of the verb bark here?
Being a native speaker, I fully understand the normal meanings of the verb bark relating to making a loud animal-like noise. However, this does not intuitively seem to be the meaning of the word in this idiom to me. Obviously, there is also the issue of the fact that bark also appears on trees, so I wonder if to bark up a tree is to shimmy up a tree by gripping onto its bark. I have no idea. I haven't been able to find any definitions of the verb bark that don't relate to making a noise.
Is to bark up something really just to make dog noises upwards towards it?
Any answers with references/sources greatly appreciated.

Here are the definitions of bark from Oxford Dictionaries Online

bark
verb

[no object] (of a dog, fox, or seal) give a bark:

‘a dog barked at her’

1.1 (of a person) make a sound resembling a bark:

‘she barked with laughter’

2 [with object] Utter (a command or question) abruptly or aggressively:

‘ he began barking out his orders’

[with direct speech] ‘Nobody is allowed up here,’ he barked.

2.1 US [no object] Call out in order to sell or advertise something:

‘doormen bark at passers-by, promising hot girls and cold beer’

A:

I've always understood the meaning of bark to refer the noise produced by dogs. Etymonline appears to confirm this:

in reference to a dog sound, Old English beorcan "to bark," from Proto-Germanic *berkan (source also of Old Norse berkja "to bark"), of echoic origin. Related: Barked; barking. To bark up the wrong tree is U.S. colloquial, first attested 1832, from notion of hounds following the wrong scent.

The Phrase Finder appears to be on the same page:

The allusion is to hunting dogs barking at the bottom of trees where they mistakenly think their quarry is hiding.
The earliest known printed citation is in James Kirke Paulding's Westward Ho!, 1832:

"Here he made a note in his book, and I begun to smoke him for one of those fellows that drive a sort of a trade of making books about old Kentuck and the western country: so I thought I'd set him barking up the wrong tree a little, and I told him some stories that were enough to set the Mississippi a-fire; but he put them all down in his book."

The phrase must have caught on in the USA quickly after Hall's book. It appeared in several American newspapers throughout the 1830s; for example, this piece from the Gettysburg newspaper The Adams Sentinel, March 1834:

"Gineral you are barkin' up the wrong tree this time, for I jest see that rackoon jump to the next tree, and afore this he is a mile off in the woods.

According to WOOFipedia (www.woofipedia.com), the expression derives from the practice of hunting raccoons with trained hounds:

Settlers of the American wilderness depended on the raccoon as a steady source of meat, fur, and fat. Frontiersmen bred uniquely American hounds that specialized in tracking and treeing the nocturnal carnivore. Coonhounds pursue their quarry through woods and swamps until the raccoon scoots up a tree. They then bay and bawl loudly to indicate their location. Sometimes, though, the wily raccoon fools its pursuers and the hounds literally bark up the wrong tree.

Just a bit of year-end fun: 
 
(lowres.cartoonstock.com)

