Run the engine for 45 seconds to 1 minute, then use a 7/8 in. wrench to spin it off. Depending on how long the sensor has been in place, you may have difficulty removing it without heat.
Use nickel-based anti-seize lubricant on the threads of the new sensor if it doesn't have it already.