I don't think it is really that complicated. On boot, a piece of embedded software (that can't be overwritten) does a checksum of the current software installed. If the checksum doesn't match the original, then it sets an internal bit to 1 to mark that the software has been changed. That internal bit can't be set back to 0, so the car is essentially marked as non-licensed and now can't be legally driven on the road.

Checking for non-licensed modifications is simply checking if that bit is set. Implementation would be a little more complex then the above, but similar technology already exists and is in use. The result is that modifications would be possible, but driving the resulting car on public roads would not.

A system for allowing new software to be placed on a car could be setup, but it would still require re-licensing the whole car so it wouldn't necessarily be an easy process.