Shambles, check out "Arkansas Boys" in the database. Essentially the same song, different states (Missouri/Arkansas). A note there indicates that an earlier (perhaps original) version was about Virginia/Carolina. Apparently, in time-honored fold tradition, one plugs in the names of the states one wishes to uphold/castigate. I have seen a version called "Kansas Boys"--can't remember what the other state was. I've been told that the East Virginia/West Virginia version was in response to the American Civil War, which was when West Virginia (pro-union, anti-slavery) separated out of Virginia, which seceded the union and join the Confederacy.

As mentioned, East Virginia is not a state. I imagine the term was used to indicate the state of Virginia for a while after the state of West Virginia was created in order to minimize confusion. It's also possible that some use the term to mean eastern Virginia.

Also in the database is a version of "East Virginia", referred to by Pixie and Jon--same opening line(s).