As you probably already know, California is a very dog-unfriendly state--their state parks forbid dogs on trails.

Dogs are also forbidden on trails in US National Parks. There are a few rare exceptions (on the Pacific Crest Trail in Crater Lake, Mt. Rainier and North Cascades National Parks) but the dog must be on leash and stay on the trail. That isn't to say you can't take your dog to a national park, but you have to stay in the parking lot and campground areas and keep him on leash. I was very happy to find that I could take my dog on paved trails in Yosemite Valley (as long as we stayed on the pavement, said the ranger), but this is unusual, and that's not a backpacking area.

A few heavily used areas in US National Forests prohibit dogs--the Enchantment Lakes area of Washington State is one. For the most part, though, dogs are allowed on National Forest trails. In some areas they must be on leash and in all areas they must be under control. If your dog doesn't come when called no matter what the temptation (chipmunk right under his nose) then he's not under control and should be kept leashed. (My Hysson regards "come" as an optional command, but he comes right to my side when I tell him to "heel." On the other hand, he's a wimpy dog who is too scared of chipmunks to chase them.) You pretty much have to check the regulations for each National Forest you'll be in. I believe the US Bureau of Land Management (which manages the majority of public lands in the West) has looser regulations except in a few high-use areas.

Oregon and Washington state parks are dog friendly but require leashes. For other states, you'll have to check--each state is different. The same is true for state forests (more common back east).

When do you plan to go? Most prime backpacking areas in the western US are in the high mountains, where winter is already arriving. You won't be able to get there until next summer. Areas I've been that I recommend (but not until next July!) for outstanding scenery include Washington's Glacier Peak Wilderness and Wyoming's Wind River Mountains.

EDIT: I thought I'd seen and responded to this question before--I already answered your query on BPL. So if this post sounds like repetition, it is!