I would remove the top and bottom so you have that flat surface again when you are done. It's really just a matter of removing all the old staples and then starting over with the new material.
I've found the fastest way to remove staples is to take a small chisel or something sharp with a handle and slightly dig under the staple, then lift up. Then just grab the staple with any type of pliers or sire cutters to pull them out. It is tedious and my least favorite part. If it didn't need to be transparent I would probably cover over the old cloth, it's a lot easier.
Greg