(Solid) tip "tinners" are almost always ammonium phosphate with some tin (or tin-lead) bits mixed in. They are moderately aggressive at cleaning oxides off, so shouldn't be used constantly, but only when needed. The best tip tinner is your solder--tips should always be coated with a small amount of solder.
If some of the oxides are just sticking really well, you could try to mildly abrade them on a brass sponge, copper braid, or similar, but you can't be too hard or you will damage the iron plating (good tips are typically copper core, plated with iron, then chromium everywhere but the working area).
Practice good tip care. I use a Hakko iron and tips at work and mine has lasted about a year (moderately light use, maybe 5-6 projects). Put a good amount of solder on the tip when storing it or leaving it idle for any length of time; don't, for instance, wipe it off, put it in the holder, then leave it on over lunch.
Additional guides:
After doing plenty of research and asking some electrical engineers who use them, I've found some points that were helpful in deciding.
Benchtop desoldering or rework stations tend to have the most accurate temperature controls, best thermal recovery, and extra features like programmable timing and hot-air, etc.
For example, if you plan to remove surface mount IC's on a regular basis, a hot-air rework unit may be ideal. They have nozzles for just about every IC package, and the higher end units can be programmed to pre-heat for a specific number of seconds, then heat for a number of seconds, and some have a vacuum nozzle to pick up the now-free part. (For example, see the Hakko FR-803B, a $1300 unit.) You have to weigh the cost heavily with the amount of desoldering or repair work you expect to do. For the occasional removal of parts, on a hobby level, this is likely overkill.
If you're just looking for a step up (or two) from the soldering iron and vacuum pump or solder braid, self-contained desoldering guns like the Hakko 808 can be found for about $200. While it has less fine control over temperature than a bench unit, it does have several benefits: self-contained vacuum pump, replaceable filters, and highly portable. Unless you have specific requirements for performing repair work, it will probably handle any through-hole work.
There are many online videos and tutorials about surface-mount desoldering. It is more tricky than through-hole for a variety of reasons. If you have to desolder SMT, you will want to check some of them out first. Some irons have tips specifically designed for multi-pin SMD packages, there are also hot tweezers and of course the aforementioned hot-air rework systems.
To recap, here are some solutions for desoldering through-hole and their relative price ranges:
The old desoldering pump, for about $15-20. Works "ok" but requires both hands and sometimes creative angles.
$12 at Radio Shack, requires one-and-a-half hands. I've not used one, so I'm not sure if it would be more or less convenient than a separate iron and pump.
Between $50 and $200. I found some for $50-100 online, but I have actually tried a Hakko 808 and can attest to the performance. Great for through-hole.
$400 and up. Lots of brands to choose from, Metcal, OKI, Hakko, Weller, etc. Once you start looking at stations, a variety of features and use-case scenarios start to emerge. Definitely geared more for commercial and industry use where soldering rework is an everyday occurrence.
One important thing to look for in soldering or desoldering equipment is the availability and price of consumables. Filters, tips and nozzles. They will need replacement. If you find an off-brand version, can you find parts for it later? If you get a quality station for cheap, do the replacement parts cost a fortune? Can they only be ordered from a foreign country?
Many manufacturers provide documentation and videos of desoldering equipment. Take some time to go through them, realistically evaluate what you will use (and what you can afford).
When I started looking, I thought I wanted a dual-port station (one solder, one desolder). Such stations are about $600. I probably am not going to desolder daily. I went instead with a single-port soldering station for $300, and a desoldering gun for $200. For my shop, the portability of the desoldering gun is worth the $100 saved and then some.
Best Answer
One thing I haven't seen mentioned yet is this: Whenever you are planning on not using the iron for more than about a minute, load the tip with solder. This way, the solder oxidizes in the air, instead of your tip. An unprotected tip will start to oxidize pretty quickly in air, and the longer it is allowed to do so, the worse it gets.
When you are ready to use the iron, do the following:
Tips oxidize dramatically faster when they're too hot, so check your temperature if you can.