As Dracko mentions, the level of Fort Level present determines if you are able to navigate the river or not. However, it's not as straight forward as having a holding with 10 Fort Level present. Looking at the code, it seems like it currently calculates an average for all neighboring provinces, and that average cannot be more than 10 for you to navigate it.
I'll file an improvement in our bug database for actually adding this information to the game somehow and make it more clear as to why you may, or may not, navigate a river.
I'll file an improvement in our bug database for actually adding this information to the game somehow and make it more clear as to why you may, or may not, navigate a river.