c. 1300, herber, "herb garden, pleasure garden," from Old French erbier "field, meadow; kitchen garden," from Latin herba "grass, herb" (see herb). Later "a grassy plot" (mid-14c., a sense also in Old French), "shaded nook, bower formed by intertwining of trees, shrubs, or vines" (mid-14c.). It is probably not from Latin arbor "tree" (see arbor (n.2)), though perhaps that word has influenced its spelling:
[O]riginally signifying a place for the cultivation of herbs, a pleasure-ground, garden, subsequently applied to the bower or rustic shelter which commonly occupied the most conspicuous situation in the garden ; and thus the etymological reference to herbs being no longer apparent, the spelling was probably accommodated to the notion of being sheltered by trees or shrubs (arbor). [Hensleigh Wedgwood, "A Dictionary of English Etymology," 1859]
But the change from er- to ar- before consonants in Middle English also reflects a pronunciation shift: compare farm from ferme, harbor from Old English herebeorg.