Where do these nut-brown maids come from? Well, it doesn't hold true for "Lord Thomas" (where the brown girl is the one with gold and gear) but there can be a natural association with the out-of-doors. "Ho-ro, my nut-brown Maiden" (as translated from the Gaelic in the popular Scottish Students Songbook) contrasts Highland Mary, 'down from the bonnie glen', to Lowland maidens in "Glasgow and Dunedin" (Dundee?). In German folksong I think the association is even clearer. Sorry I don't have the song at hand, but at Sunny Camp last weekend there was a great German song session and I seem to recall a popular one about "mein schwarzbraun Madel" -- eyes, hair and (implied, I think) skin because the song had a lot of woodland (and gypsy?) references. (Damn, now I have to look it up. . . )