The supply AI will generally attempt to use infrastructure of level 7 or over, if available. Making a couple of Level 10 supply highways across Poland is pretty close to a necessity, no need to upgrade all of the other provinces, although in some cases the AI will push supply through provinces adjacent to the main route if there's not enough throughput on the main route.
Use the Supply map overlay to see where the AI is routing the supplies to your troops on the Soviet border, then build up the weakest links along that route first., gradually improving it to Level 10. There's generally a bottleneck just below Lithuania, if the Soviets haven't annexed them before you launch Barbarossa., where even Level 10 isn't quite sufficient, so you may need to make a double-wide path for a few provinces. You can generally build two main paths across Poland, one above and one below the Great Priyapet Marshes, branching them and extending them into Soviet territory as the invasion advances. The main point is, keep an occasional eye on the supply map and see where the AI is sending the supplies through, so you're not wasting IC improving provinces which don't need it.
Limiting north-south movement along the Soviet front will keep the AI from cancelling the current supplies in transit for that unit and sending fresh supplies all the way from Berlin. A province or two is fine, as the AI will merely change the path over the last province or two, but much more than that and it may create a new route,
jkk's point about Practicals is something to seriously consider. Building a few IC (as in 10-20) before starting to produce mass quantities of combat units can boost your Construction Practical, and is still supportable with Germany's access to raw materials,. Building infrastructure later will be considerably faster and cheaper, particularly if you research a level or two of Construction Theory so it doesn't decay as quickly. It also means that you're not building large numbers of combat units immediately, then having to supply them for 3-4 years before they see action. Building a SMALL number of units over time can ramp up your Practicals, so they're cheaper and faster to build when you do start cranking them out. in mass quantities.
The best illustration of the importance of Practicals is in building a German navy. Lay down the keel for a new Battlecruiser in January of 1936 while you research main guns for capital ships, then start a second BC around 4-5 months later. You can start building your first actual BB once the tech for main guns is done, and a second a month or two later. The first BC will eventually complete, and its effect on Capital Ship Practical may be high enough to force the completion of the second BC the next day, saving 4-5 months of IC which you would otherwise have wasted by building them simultaneously. The BBs should both complete before the start of hostilities, again saving months of IC/days as a result of the subsequent builds completing sooner. This effect, duplicated on Construction by building IC and upgrading airfields and infrastructure in Germany in 1936, should make the cost and completion time of an ambitious infrastructure highway across Poland relatively reasonable.
