The regional governers would then take over, as was mentioned in ANH (and subsequently used in the EU.)
"Jokes aside, if they both died the Empire would be over. I mean, remember ROTJ??"
Interestingly enough, the novelization makes it clear that the Empire was under the control of Palp's Force abilities, which would explain its machine-like efficiency. After Palps is killed, the armies, which were too dependant on this control, fall into disarray, and are able to be overcome by the Republic forces. (A very similar concept was used for the droid armies in TPM.)
While the movie doesn't touch on this, you may notice that the Republic doesn't start kicking butt until after Palps is killed.
