Pin down a corner with your knee, smash the ever living crap out of that corner and peel the upholstery off. Do it until the middle, do the same for the other corner, when you have both corners off twist the upholstery 90 degrees and then slide it down the middle rail. It's a pain in the butt and you will have to fluff up the headrest when you install the newer one, which will be reversed from what I just told you and harder than removing the old one.
The thing to be careful on is that you don't rip the new middle slit when you install the new one. The trick is really in twisting it on and scrunching the foam in on the corners when installing it.
Hope that helps, it's been a while since I've installed them but I've installed several sets and the last set I installed was gravy compared to the first time I fumbled around with them.