Easy. In the source code add a conditional. For example, if the protocol were needing to be changed for all verifications after block 200,000 then the pseudo code for that is:
If block <= 200,000:
# Do it the old way.
# Do it the new way.
The problem isn't technical it is political. If that change causes me pain (e.g., inflate the currency at a higher rate) then I am not going to want to accept any version of the code that does something that I don't want to see happen.
So any change needs to get buy in (concensus), from the developers, miners and ... most importantly, those who will accept bitcoins under the new rules in exchange for something of value.
If an unwanted change is pushed forward without being widely accepted, a blockchain fork will occur, and the losing side (generally the fork with the new rules) essentially gets ignored as if it didn't even exist by the rest of the network.
There have been several changes to the protocol as well as changes to the implementation in the client. Some are planned well in advance (e.g., BIP 16), and some are in response to a problem (e.g., Aug 2010's value overflow).