Hey, ich weiß nicht, ob du jetzt schon gefahren bist - ich bin aber vermutlich einer der Holland-Experten hier im Forum, denn ich lebe in Rotterdam. Fahrradwege oder -spuren wirklich immer nutzen - es gibt auch fast nie einen Grund, das nicht zu tun.
Der Rhein geht nach Rotterdam (der heißt nur ab der niederländischen Grenze kaum noch irgendwo Rhein) und ist vielleicht auch nicht unbedingt die interessanteste Strecke. Je nachdem, wo du über die Grenze willst: Ab Venlo würde ich mich zunächst nach Den Bosch orientieren, dann über Heusden, Woudrichem, Schoonhoven, Gouda und von dort nordwärts an Alphen vorbei Richtung Amsterdam. Ab Nijmegen solltest du den Utrechtse Heuvelrug zwischen Wageningen und Utrecht mitnehmen und von Utrecht aus ein Stück entlang der Vecht fahren. Ab Arnhem würde ich über die Hoge Veluwe nach Amersfoord fahren und dann weiter durch den Wald nach Hilversum und nordwestwärts Naarden und Muiden am Ijmeer mitnehmen.
Strecke planen bei GPSies.com. Alle straßenbegleitenden Fahrradwege sind eingetragen. Die sind überwiegend asphaltiert - zwischen Orten sowieso, in Orten meist. Manchmal gehen sie da aber auch über geklinkerte Parallelstraßen - das erkennt man auf der Karte daran, dass es ein Radweg auf einer kleinen Straße neben einer Hauptstraße ist - im Zweifel mit Streetview nachschauen, wenn man das vermeiden will. (Fährt sich aber, wenn's wie üblich vernünftig unterhalten wird, so wie Fußweg mit Platten, nicht wie Kopfsteinpflaster.) Bei GPSies.com siehst du auch rote Fahrradrouten - das sind die touristischen, nummerierten Landesrouten mit Namen. Außerdem gibt es das Fietsknooppunten-Netzwerk - da fährst du von Zahl zu Zahl, findest an jeder Zahl eine Karte und Entfernungsangaben und fährst durch schöne Gebiete - aber nicht immer den direkten Weg. Die roten Wegweiser, die du überall sehen wirst, geben stattdessen üblicherweise den direktesten Weg.