River King was the title held by an ancient, and now extinct, local dynasties that ruled over the Riverlands.
The River Kings were never very strong, because they were surrounded by enemies on all sides, bordering every other kingdom except for Dorne, with no significant natural barriers against them. To the southeast, they faced the Storm Kings of House Durrandon. To the southwest, they faced House Gardener from the Kingdom of the Reach. To the west, they faced House Lannister from the Kingdom of the Rock. To the northwest, they faced devastating raids by the ironborn from the Iron Islands. To their east, they faced House Arryn from the Kingdom of the Mountain and the Vale. Across the Neck, they even faced the Kingdom of the North (though the kings of House Stark rarely advanced south of Moat Cailin).
Over three centuries before the Targaryen Conquest, the River Kings were completely conquered by the Kingdom of the Stormlands, and House Durrandon extended its control all the way north to the Neck.
About three generations before the Targaryen Conquest, however, the Riverlands were captured from the Storm Kings by the Iron Islands, under King Harwyn Hoare. The ironborn were even more brutal than the Storm Kings, reducing the Riverlanders to thralls and forcing them to build Harrenhal - yet no sooner was Harrenhal completed than the Targaryens invaded and killed Harwyn's grandson Harren Hoare, along with all his sons. The Targaryens then raised up House Tully - who were unrelated to the old River Kings nor had ever been kings of any kind - to rule the region under them as Lords Paramount of the Trident.
In the books
In the A Song of Ice and Fire novels, it isn't entirely clear if the "River Kings" ruled all of the Riverlands. At one time or another, House Mudd, House Fisher, House Blackwood, and House Bracken claimed to be kings. The Brackens claim that they were kings first (in the millennia-long, legendary past) but then the Blackwoods overthrew them, while the Blackwoods claim that it was the other way around. House Mudd was based around the Blue Fork of the Trident River, and was said to rule between the Neck and the Trident, but a large portion of the Riverlands extends south of the Trident. It also isn't clear if the Mudds managed to subdue the Blackwoods and Brackens, to the southwest along the Red Fork of the Trident). The upcoming World of Ice and Fire sourcebook should sort this out.
Based on George R.R. Martin's comments, it vaguely appears that House Fisher ruled first, but was defeated by the first great wave of ironborn expansion, one or two thousand years ago. House Mudd drove the ironborn out when this first era of expansion ended, but the Mudds were later conquered by the Storm Kings about 360 years before the Targaryen Conquest. Some three generations before the Targaryen Conquest, the ironborn entered their second great age of expansion under House Hoare, who captured the Riverlands from the Storm Kings.