I've biked between Duluth and Madison, though in separate stages over the span of several years.
Getting out of Duluth, a great way is the Munger Trail, a rail trail that's about 70 miles long. It heads southward to Hinkley:http://www.dnr.state.mn.us/state_trails/willard_munger/index.html
From there, you can ride on 61 south to North Branch, and pick up another trail, the Sunrise Prairie, which parallels 61 south for about 17 miles to Forest Lake:http://www.traillink.com/trail/sunrise-prairie-trail.aspx
At this point, you are in the Minneapolis-St. Paul suburbs. You can bypass the Twin Cities and hook up with the Northern Tier which will bring you south through the Mississippi Valley, or take WI 35 down to Marshland and hook up with the Great River Trail. This is the start of a series of four interconnected trails totaling 100 miles in length, and includes the La Crosse River, Elroy-Sparta (the Grandaddy of all
rail-trails0, and the 400.
This will bring you to Reesburg, WI, which is about another day of riding to Madison on back roads. I don't exactly remember the routing from there (and probably didn't take the best route) so I'll let someone else follow up.