Surely they had to get some sort of permission to carry those shows; I've read in many cases, certain pre-empted shows had to air during certain times of the day (such as daytime shows had to air before 5pm local time or earlier). Also, it also comes down to compensation issues...the business model was (and still is, in some cases) that the networks paid the affiliates to carry their programming. Otherwise, it doesn't make sense to pay an affiliate when they don't carry certain programs.
Yes, the network would have to approve an alternate station and any compensation. Also the network would be responsible for getting the feed of the show to the alternate station (I.E. ordering an AT&T feed to that station).
There were, however, regulatory issues involved, as well. In the latter part of the sixties, the FCC put in place a rule requiring that uncleared network programs be offered to any independent stations in a market. The rules didn't preclude the network from placing reasonable restrictions on those programs (ie, the independent station being required to carry the show in the time slot specified by the network, and not delay the show). It also didn't require that the network offer the independent station any compensation for carrying the rejected program.
So, yes, terms of carriage would be negotiated between network and station -- but the network didn't have unlimited control over the terms.