California is a very dog-unfriendly state; dogs are forbidden on trails in California state parks. This is not true with parks in other states that I've encountered. Generally, though, dogs must be on leash.
US National Parks nationwide forbid dogs on trails. The only exceptions I've found are the paved trails on the Yosemite Valley floor and on the portions of the Pacific Crest Trail that lie within Crater Lake, Mt. Rainier and North Cascades National Parks.
Some sections of some national forests are closed to dogs (such as the Enchantment Lakes section of Washington's Alpine Lakes Wilderness), but for the most part dogs are welcome on trails in US National Forests, whether inside or outside wilderness areas. They are often required to be on leash and are always required to be under your control. If your dog won't come to you immediately on command regardless of the temptation (such as a squirrel right under his nose), then he's not under control!
Basically, taking a dog out backpacking is like taking a child--you have to hike his hike, not vice versa. The difference is that the dog, unlike the child, will often keep going to please you if he is hurting or overtired, so you have constantly to assess his condition. A child will have a meltdown when hurt or tired, something dogs normally don't do!
Note that for your cross-country trip, dogs are hardly ever allowed on public transit. You'll basically have to use your own car. If you're hiking the American Discovery Trail or one of the north-south border-to-border trails, you will inevitably find some jurisdictions that you'll have to bypass or arrange care for your dog because dogs are not allowed.
A lot of the best backpacking trails in the western US are in the mountains and are already starting to receive winter snow. Had you thought of doing this next year?