i took fly-fishing gear with me when i biked the TransAm back in 2007.
i was def glad i brought it along as there were some hot days where last thing i wanted to do was be biking in mid day and opted to wade in a river and fish.
not that i'm saying not to buy a license but....i didn't buy any mainly b/c the streams are so remote, esp the more west you get you run into no one....plus, if you're not keeping the fish who cares.
i was able to catch fish in nearly all the states out west (kansas not so much).
i'd say, if you like to fish, a bike trip is a great time to carry some gear along....it's a great way to break the day up, esp on a lunch break....plus it provides you the opportunity to catch fish native only to certain areas of the U.S.
i.e.: catching 4 wild cutthroat trout in middle of nowhere Montana is something I can't quite reel in back home in Virginia.
do some research on some of the bigger streams you might come across and maybe a guide for half a day would be a cool thing to do....
hope this helps some.