1st, make sure your plugs, timing, ignition, etc are all ok.
2nd, check for stored codes in the ECM (or maybe do this first, since it's easiest).
3rd, if you're "pretty sure" the O2 sensor is bad, it's probably a good time to replace it and they don't cost that much anyway.
I had an O2 sensor which had rusted through but still worked (!). A slight twist with a screwdriver dislodged the core of the thing leaving the "nut" portion behind. After I replaced it, I noticed some improvement in power.
After all that (which is the obvious stuff) it gets esoteric. It could be a vacuum leak. It could be a leaky or bad injector. It could be something in the distributor. It could be your transmission, if you've got auto.
heck, it could just be age--low compression, or something.
Anyway, for what it's worth...I've had mine a little over a month and I'm still learning, but this is the stuff I'd check, and in approximately that order. Other more experienced folks might have more (or more specific) advice, but I cannot resist sticking in my $0.02 when I think I can offer some help... 
Ed
PS oh...not just the injectors; the fuel pressure might be an issue, too, tho I'm not sure how.
