Is this one of those Toyota O2 sensors with the two little nuts?
Usually by the time those nuts need to be removed they're a lot smaller and rounder than they used to be. Find a socket that's too small to fit and try to hammer it on. If you get the socket on, take it back off and try to hammer on a smaller socket. Use a socket that won't go on so you can hammer at it until the rust starts to break up a little. Once you've done that you should be able to use a fluted bolt removal socket (socket that fits round-head bolts) to take it right off.
If the nuts are just too small to do that use a tiny straight screwdriver to peel the nuts off the studs.