heat resistant wiring, i would look for automotive quality, im not sure what 'grade' that is. make sure it's the same guage as the old wires. also, be sure to use solder with flux, o2 sensors are voltage specific, any other methos other than soldering you may have voltage issues. and solder them correctly, or have some with experience soldering correctly help you.
edit: oops, you can buy automotive electrical wires from almost any parts store, just make sure you know what guage is correct.