Well, i'm not the most knowledgeable but I am willing to reply:
When my o2s were bad it wouldn't throw a check engine light, however, when I ran the OBD I test it would come up with an HEGO system lean code, I ended up replacing them both, cost about $60 each.
Testing the O2 sensors involves probing the sensor leads underneath your car, be careful its hot down there, on our cars it is a 4 hole sensor with the following arrangement:
GND B+Volt
SIG HTD GND
Allow the car to warm up to operating temp and then probe between the GND and SIG, this should produce a varying signal voltage between 0.1 and 0.9 volts once the car is at normal operating temperature.
You can also test the O2 sensor heater by probing the B+volt and HTR GND, this requires assistance as the signal is only sent for ~3s have someone turn the key to the "on" position and obseve the voltmeter you should observe some change in voltage.
If either of these tests fail you car is most likely running in an open loop mode, wherein the O2 sensors are being completely bypassed and air/fuel mixtures are being calculated based upon preprogrammed values.
I'm curious what you're original fuel mileage was, as it seems to me that even with the O2s in the open loop mode gas mileage shouldn't be down THAT much. I guess its possible, and like I said I don't know too much about it. I'd say if you have the money, swap 'em out, its not too hard and I am sure you are getting up there in miles to where its not a bad idea.
I'd also check all of the fuel lines for leaks, I had a clogged up fuel filter as well and that was a quick and cheap job. Could be dirty/clogged fuel injectors and so on and so forth...its a treasure hunt.
Hope this helps a little...best of luck!