The line in question seems to be only adding some visual imagery to the poem. One of the two roads the speaker was considering following was obviously not used very frequently because it was covered with leaves which had not been trampled on by people wearing muddy shoes. This suggests that it was the time of year when most of the trees in New England shed their beautiful leaves and cover the ground. The speaker--presumably Frost himself--chooses to take the road that is covered with the leaves that have not been "trodden black" by the majority of travelers. In other words, the road he chooses to take is not "the road not taken." The road not taken by the speaker is the one which most travelers have obviously taken because the leaves are trodden black. But he wonders where he would have ended up if he had taken that road. The poem is about the road he didn't take and not about the road he took.
The phrase "trodden black" is very good because it not only describes the color of the leaves but suggests how they have been mashed down and destroyed by countless feet. It also suggests that there is something rather ugly about that road, which may explain why he chose the other one rather than following in the footsteps of a lot of trudging drudges on their way to routine jobs in some big city.