Some good points have been given already especially as far correct spark plugs and correct fuel go. Some other points, unfortunately, I can only describe as regurgitated 'car-care' sales drivel. I'm almost surprised that no one has mentioned that you should wax your car more often.
Here is a list of things that are not worth your money and time:
Changing oil more regularly that specified by your manufacturer. They knew about sludge formation when they specified the intervals, so that wont be issue. Do you really think that any change in fuel consumption due to slight changes in friction will cover the cost of the extra fuel?
Air filter. Clogged air filters are an obstruction to airflow and reduce maximum power output. This doesn't translate to reduced economy because, unless your highway driving is very different to mine, you probably cruise with a much more extreme air intake restriction already. It's called a throttle valve. If tomorrow you replaced your clogged air filter with the best flowing air filter you can find, you may gain some power, but to cruise at the same speed you would have your throttle slightly more closed in order to achieve the same manifold pressure, and thus the same output torque as required for cruise. No gain in economy. Here's a source: http://www.fueleconomy.gov/feg/pdfs/air_filter_effects_02_26_2009.pdf .
Fuel filter. Replace this as specified in your manual, as a blocked filter may case lean burning in wide open throttle, resulting in possible engine damage. However, if the filter was flowing so badly to affect fuel mixture at cruise (where something like 30hp is required) your engine would misfire at full throttle. Extra consumption due to extra fuel pump work is not going to be measurable; it'll still be drawing powerless than your headlights.
Tyres. Yes some tires are more efficient, but please do yourself a favour before dropping any money on new tyres and calculate how long at will take for the savings in fuel consumption to add up to the extra money you pay. I suspect that the answer will be longer than the service life of the tyre.
Now to address possible reasons for your increase in mileage:
Some, if not most, of your loss of mileage is from irreversible engine wear. I'm sure you already know this. You've lost some compression due to piston ring and valve seat wear. You wont get that back.
There are also some losses in mileage that you can recover, but diagnosing the sources of the losses might be quite labour intensive, so it will probably only be worth doing if you do the diagnosis yourself. Buying an OBDII scanner is a good start.
Here are the first things I would be looking at:
Oxygen sensor. This is the sensor that the ECU uses to determine that the fuel/air ratio it thinks it is supplying to the engine is actually being supplied. It is usually the ECUs only feedback about actual combustion. As they age oxygen sensors slow down in their response time and eventually the ECU will throw a Check Engine Light, but not until a significant drop in performance of the sensor has already occurred. There may be some sense in replacing an old O2 sensor before the CEL is thrown, however it may be a good idea to check its performance first. Here is a good resource on that: http://www.autodiagnosticsandpublishing.com/feature/o2-sensor-testing.htm.
Injector cleaning. Injectors slowly clog up and their flow rate is reduced with time. Unfortunately not all of them clog up at the same rate, causing some cylinders to run leaner that others. Because of the way oxygen sensors work even the slightest lean condition on one cylinder will cause the sensor to read lean, causing the ECU to run all of the other cylinders rich in compensation. Some people have had luck improving uneven injector delivery problems with concentrated over-the-counter fuel injector cleaner in the fuel tank. Your (figurative) mileage may vary, but this may be a good place to start before delving into deeper diagnosis.
Also: Cruise speed is probably the biggest change to your driving behaviour that you can make. I almost doubled my mileage when I had to limp home 400km with almost no effective headlights after a nighttime kangaroo collision.