Old English paþ, pæþ "narrow passageway or route across land, a track worn by the feet of people or animals treading it," from West Germanic *patha- (source also of Old Frisian path, Middle Dutch pat, Dutch pad, Old High German pfad, German Pfad "path"), a word of uncertain origin, not attested in Old Norse or Gothic.
The original initial -p- in a Germanic word is an etymological puzzle. Don Ringe ("From Proto-Indo-European to Proto-Germanic," Oxford 2006), reflecting an old theory, describes it as "An obvious loan from Iranian ..., clearly borrowed after Grimm's Law had run its course." Watkins says the word is "probably borrowed (? via Scythian) from Iranian *path-," from PIE root *pent- "to tread, go, pass" (source of Avestan patha "way;" see find (v.)), but this is too much of a stretch for OED and others. In Scotland and Northern England, commonly a steep ascent of a hill or in a road.
"to walk, travel on foot, tramp slowly or wearily along," 1550s, probably from Middle Dutch paden "walk along a path, make a path," from pad, pat "path" (compare path). Originally a cant word among criminals and vagabonds, perhaps of imitative origin (sound of feet trudging on a dirt road). Related: Padded; padding. English also formerly had the noun pad meaning "path, foot path" (1560s), which might be from this verb, or from the Dutch noun, or a variant of path.
"So they call me, young woman, and many a great lord has got a title that he did not half so well merit; though, if truth be said, I rather pride myself in finding my way where there is no path, than in finding it where there is. But the regular troops are by no means particular, and half the time they don't know the difference between a trail and a path, though one is a matter for the eye, while the other is little more than scent."
[Cooper, "The Pathfinder"]
"highwayman who robs on foot," 1680s, from foot (n.) + pad "pathway, footpath" (1670s), from Middle Dutch pad "way, path," from Proto-Germanic *patha- "way, path" (see pad (v.1), and compare path). Pad was a cant word among thieves and vagabonds, in expressions such as stand pad "stand by the wayside begging." Especially "one of a large class, existing in Europe when police authority was still in an ineffective condition, who made a business of robbing people passing on horseback or in carriages" [Century Dictionary].