Darover,
the O2 sensors (pre-cat - the only ones that matter for mixture control) should last 100k. The older type sensors on OBD1 cars and before would need to be replaced sooner ~40 - 60k miles, but you shouldn't have to replace these O2 sensors that soon. Doesn't hurt to do them - new sensors result in a leaner mixture, and will likely pay for themselves over acouple years - but it should not cause a very noticable difference in your MPG.
Does the car drive fine - top end power OK? Seems if your mileage changed that drastically, then you should have a really rich-running condition. Do you see black smoke from the exhaust on acceleration? That would be a sure sign of a rich mixture... Any leaks in your fuel tank?

Piotr