For 80 lbs, standard 2"x4" stock should work perfectly. I work with a community theater group and we use 2x4 frames for platforms that have people not only walking, but dancing and jumping around on them. We've never had a failure yet, even after many shows of abuse!
Seeing as it will be exposed to the elements, get pressure treated as well.
Just make sure you use good bolts (9/16" size, Grade 5, but G5 might be overkill). You should also add some eye bolts (say 4 per side, with shanks that go at least 1.5" -2" into the 2x4) so you have plenty of mounting points for tie-downs. More thank likely, you'll end up using the rack for more than just your canoe.