For those who aren't familiar with the Gimp's "Color to Alpha" feature yet, here is the page on it from the Gimp's documentation: Color to Alpha. It does a really good job, and I wonder much how exactly Gimp does it in terms of color manipulation, whichever color space the colors might be in. Thanks a bunch for any hints.
EDIT 1: Generating transparency information for a pixel based on its similarity to the key color (the one you select in the "Color to Alpha" dialog), like some folk suggested before removing his answer for some reason, would sound like a good insight, but I suppose it's more intricate than that. Let's assume we estimate color similarity in the unit range from 0.0 to 1.0 and we've got a pixel whose color is, for example, 0.4 similar to, say, the color of white (like you would have selected white in the "Color to Alpha" dialog) and therefore the pixel gets an alpha value of 0.6, then how would you alter the pixel's actual color to compensate the loose of brightness/luminosity/saturation when the resulting pixel is displayed against a white background with the alpha of 0.6?
EDIT 2: Actually an update: The sub-question related to the first edit has been answered in How to change the alpha of a pixel without changing the resulting color? but it's probably not the full story because what is going on in the Gimp's source for the "Color to Alpha" feature is not that simple and seems to be based on a specific algorithm rather than a formula.
You need to come up with a mechanism for comparing the similarity of colors. There are a variety of color spaces in which you can do this. RGB is often not the best for this sort of thing. But you could use HSV, YCbCr, or some other luma/chroma space. Often a distance in one of those spaces will give you a better answer than a Euclidean distance in RGB. Once you have a distance, you could divide that by the maximum distance to get a percentage. That percentage would be the inverse of the alpha you want to use, as one possibility.
If you want to know how the GIMP does it, you can look at the source. For example, here's one recent code change to that plug-in.