In the perfect world, you just slide a wrench on the O2 sensor and it comes out. Unfortunately since its located in a "hostile" environment (lots of heat, lots of water and potential corrosion underneath) it typically gets pretty stuck, though most people eventually do have success getting it off. Careful not to start stripping it with that open ended wrench, however. Or you may not have room for a wrench, or the right size of wrench, in which case use a socket instead.
For a few people, it won't budge cold, but they just run the engine for 10-15 minutes and try it again and it budges (uses the exhaust to heat it up, careful not to burn yourself).
Another option would be to slide an O2 sensor "special socket" onto it, give it a normal crank. O2 special sockets have a groove cut out from them to go around the wires. But be careful not to crank too hard and start stripping your bolt. Some people report good luck with these, and there are some quality ones out there (you may be able to rent them from your local auto parts store). Sometimes these "grooved" sockets, for very stuck sensors, start 'splaying' and/or stripping the bolt, in which case, stop cranking on them and try something else. Some people have success using them even with extra leverage, while for a few it ends up stripping the bolt, so its unclear what exactly that point is.
I am not condoning the Tekton brand here, per se, just showing some example sockets:

Another option: leverage
Basically you're probably going to want to get a "real" socket onto it. You want either a 6 sided socket (impact socket is even better but may not be required, non deep socket is nice but deep work as well), or a 6 sided box wrench, the exact size needed (7/8 and 22mm seem to both work, oddly). To get the socket on, cut off the wired end of the sensor or break it off with a hammer, or saw it off (above the threads of course) then you should be able to put your socket on. Now you can use a breaker bar or a cheater bar and crank. You can whack the "far" end of it (leverage end) with a hammer (remember "lefty loosy" like normal), or even hit your breaker bar "far end" with a hammer, or attach a second wrench to the end of your breaker bar for even more leverage. Most advice seems to be that a "jerk" thrust (or hit with hammer) is more effective than just leaning into it. Pull don't push the lever. You can also combine this with applying penetrating oil first. "Rocking" it back and forth (alternate tighten then loosen) might be helpful. If you can fit get impact wrench on it, that might work as well (only impact wrench on the 6 sided socket, not the special O2 sockets).
Another option is penetrating oil. Here it suggests to spray it on while the exhaust "is somewhat hot" (and then apply leverage). Some spray it on once an hour for two hours. Some let it sit overnight. Possibly spray it on then turn the engine on, let it heat up, spray it again, cool down, that type of thing, anything to try and help it seep in. Tap it with a ball-peen hammer to try and create some space for the oil to get in. All while spraying and/or trying some leverage on it. You'll want to wire brush it clean as well so the lubricant can get access more easily.
In terms of penetrating oil strength, one study showed this:
No Oil used .................................. 516 pounds
WD-40 ................................... ...... 238 pounds
PB Blaster ................................... .. 214 pounds
Liquid Wrench ................................127 pounds
Kano Kroil ................................... .. 106 pounds
50% ATF - 50% Acetone mix............53 pounds
Though anecdotally Kroil was still preferred in that thread to the ATF mixture. Also mentioned but not tested "mouse milk" (its users recommended an overnight soak), brake fluid (note, bad for paint), straight ATF (automatic transmission fluid, also bad for paint), etc. Note Liquid Wrench smells better than PB Blaster, and is about as easy to purchase, and be careful, ATF/Acetone is said to be flammable. Also heard good things about sea foam deep creep.
Another option is (instead of using just normal exhaust heat) to heat up around the threads (the body around the sensor) with a torch (preferably oxy acetlyne or MAPP which burn hotter than propane). When that's hot crank it with leverage. Or heat up the threads of the sensor itself till its cherry red, let it cool, then try leverage. Or apply penetrating oil, heat, apply penetrating oil, cool, heat again, try leverage, or heat just one side of it, etc. Driving it 30 miles might get it hot "enough" (as heating it up would), as well.
When all of those fail you may want to try some of the more aggressive techniques here and in its comments (ex: wax, dry ice).
If you strip the bolt you may be able to use an "extractor bolt set" or its like to still get leverage onto the stripped bolt.
Putting on replacement
After it's out, you can either clean your old O2 sensor (if you didn't destroy it on its way out) and reinstall it, or install a new one (most common is replacement with a new one, especially since you may have been forced to destroy your old one to get it out). Check if the new one's threads have come with some thread anti-seize compound on it (bit of dark goop on them). If it does you're good to go, if not you may want to buy some anti-seize and put it on the new threads, but be careful not to put any on the sensor itself, just the threads (also don't touch the sensor end itself with bare hands). Also you may want to clean out the newly exposed receiver threads (to remove rust and corrosion) before inserting your new sensor, for instance with a thread chaser.
When you insert the new one, screw it in before attaching the electrical fastener end so that it is "free spinning" while you screw it, then attach the electrical side.
But before this all you can "test" your current O2 sensor, saw this tip "Matt's Shop You would test the 02 sensor BEFORE cutting the cord. It is so simple to test them. An open ground,dead. if it doesnt heat up, dead, use a 12volt garden tractor bulb holder with alligator wires to test the wires to the 02 sensor first. 90 percent of 02 failures is corroded wires. They cannot be repaired, ever." by "RC Hobbyist extreme"
This is a community wiki feel free to add your own tips here.