This is attributed to Bob Crandall, the American Airlines CEO of that timeframe. He was indeed a very driven individual to reduce cost and make money. This particular exploit is covered in a book called Corporate Creativity: how innovation and improvement actually happen By Alan G. Robinson, Sam Stern. The story is detailed on page 107, although there it is claimed it saved $500,000 annually! Which is significantly over most of the references I found claiming anywhere from $40,000 to $80,000 (more in line with your question). Maybe that's accounting for inflation?
This is credible, but I can't find any original documentation yet. Please stand by. In the meantime, some additional discussion. (Still no reply from the museum. Please stand by.)
I found a site that also ran the calculation and attempted to debunk or confirm this. This site mentions the more reasonable sum of $40,000 in savings, and says
Probably True- I can't find a single good source on this, but many, many news stories mention this tidbit when discussing Bob Crandall, the former chief of American Airlines who supposedly instituted this change. Granted, being repeated often doesn't make a claim true, but this one seems reasonable enough. consider just how many flights a major airline like American has per year, and how many salads they were serving back when they still served food. Now consider how small $40,000 is in the grand scheme of things for an airline that big. It's only the cost of a single employee, even less if you consider higher paid employees like pilots.
That site also references this article on MSNBC that starts off with
It’s impossible to talk about cutting airline costs without mentioning Bob Crandall, the firebrand former chief of American Airlines. And so, let us revive the olive story. Most notorious among Crandall’s legendary cost-cutting was his idea to remove an olive from each salad served to passengers. A tiny garnish would never be missed, the reasoning went, and savings amounted to at least $40,000 a year.
Given the age of this particular cost saving measure, I think microfiche may be the best way to find out for sure. I do have a question in to the C.R. Smith Museum (American Airlines history museum), and will report back here if I get a reply.
In the meantime, let's do a little math. American Airlines flies over 3400 flights a day. A quick google search for olives yielded prices from $8 to $50 for olives. Assuming American Airlines gets them in bulk, and at a discount (wholesale), let's say that an olive is only $0.01 (given what I know of olives, seems low). That means that over 1,241,000 flights in a year, they need to eliminate 4,000,000 olives to save $40,000. Let's say that less than half the flights (a nice even 500,000) have first class service that serves a meal. And that there are a total of only 10 first class seats (which on many aircraft is very low). That gets you almost 5,000,000 olives on salads. Seems conceivable with those numbers which are probably very conservatives estimates on my part that a saving could be realized (and even a slight change in per olive pricing could have vast changes). It's not the weight in this case, it's simply a material expense that Bob Crandall figured the passengers wouldn't miss.
Again, if the American Airlines history museum gets back to me, I will revisit this with a more definitive answer.