The derivation of the phrase obviously does have something to do with gardening, or more precisely, agriculture. It's original meaning, as has already been said, relates to the type of plant, fruit or vegetable which is found frequently in gardens or on "commons". (Historicaly, "commons" were the large patches of grass or woodland that ancient rural villages designated as being for the use of the community as a whole.) If such a plant is found growing in "the common or garden" it is likely to be unexceptional because of it's abundance. The phrase has since come to be applied to anything that is common or unexceptional.
(I was going to say "run of the mill" but that would be opening a whole new bag of worms, to coin a phrase).