From my research it seems the way to go is to get a cellular router and then get a sim card for a data only plan from an eBay reseller that offers a truly unlimited data plan. You have your pick of T-Mobile, VZW, and AT&T.
Right now we just tether our cell phones and use cellmapper.net to plan out where we're staying so that we have a good cellular signal.