This thread is a corollary to this previous one on access laws in different states. Although the original poster stated that Virginia access is fairly liberal, the details are much more complicated. This summary, from 1980, goes into some detail, and makes clear that stream access in Virginia is murky.

To summarize, while Virginia passed laws in the early days of nationhood making navigable waterways and stream bottoms property of the state, previously granted property rights were not forfeited by the laws. This means that if a property owner can trace his title back to the Crown of England, he can assert property rights on the waterways within his property. Of course, you may have no way of performing a 200+ year title search for every parcel of land along a river you want to float, so the determination is likely only to be made in a court of law after you have been charged with trespassing. The article is somewhat prescient, being written in 1980, giving insight on the implications of future hypothetical rulings on the Jackson River in light of the then under-construction Gathright dam, which created a desirable coldwater fishery that did not previously exist.

In a recent case concerning King's Grant claims on the Jackson River, a group of landowners and a developer filed suit against two anglers for floating on the river and fishing, which the landowners considered trespassing. While the criminal trespassing charges were thrown out, the landowners won the civil trial when the court declared they had a prima facie title to the river, river bottom, and fish, while the defendant was unable to appeal due to insufficient funds.