Did some poking around. Here's what I see:
1996: SEW started in April 1996 under a different name. Can't find any references within archived versions of SEW relating to SEO or "optimization."
Jim Rhodes's site
also started near this same time. Honestly don't know if it was before or after. He may or may not have used the term -- I have no archived versions of that site.
Northern Web's Search Engine Tutorial for Web Designers site
came in a bit later in 1997 -- no idea if they used it and I have no archives of that site.
Web Week, Cnet, Inc and the NYT all ran stories about search engine optimization that year, though the last three definitely did not use the words "search engine optimization" or make reference to "optimization." I no longer have a copy of the Web Week article, so I can't say about that. Interestingly, they did comment about things like "spamming" and "stuffing" back then.
May 1997: First reference I find within SEW to the exact phrase "search engine optimization," but only within a meta tag. It was on a page called "Search Engine Design," which I used to summarize resources about what we'd now call search engine optimization, getting listed better in a search engine's editorial results. It suggests that something was going on to make me think of using this term, though I don't see myself using it within body copy. I may have seen it in logs or posted elsewhere, perhaps in some mailing lists.
July 1997: First reference
I can find in newsgroups to the phrase "search engine optimization," from a company pitching these services.
October 1997: First reference I find to the word "optimization" in the body copy at SEW. It was on the former Search Engine Design page. I renamed that no doubt because something made me think that "Search Engine Positioning" was a better term. Reference was:
Web Ranking Tools
Bruce Clay provides a page outlining his optimization strategies.
I copy I have of his page from that time has a quote from someone saying to him:
Then, last week, I took your advice step by step. I optimized my <META> tags to take full advantage of their use.
That page from Bruce doesn't use "optimization" as a word at all. However, there's a very good chance that I drew my description from an email Bruce may have sent me about the page, so certainly making him one of the first to be popularizing it.
December 1997: First reference I found to entire phrase "search engine optimization" was in an ad that ran this month for ClientDirect, which was Paul Bruemmer's company.
August 1998: I ran an article called Promoters Call For Certification
that uses the term "optimization" several times in reference to companies. That was about an effort being led by Paul Bruemmer. Also this month, I renamed that Search Engine Positioning page to be "Search Engine Optimization."
September 2001: SEO was being used plenty by this point, but some felt it was too limiting. I suggested
"search engine marketing" to encompass both SEO and search engine advertising, and that got a good response
from my readers. I'm sure others had used the term before this suggestion. I was simply pointing out that I found it a good one.
So that's what I could find -- still no definitive first reference, but I think it's fair to say that it seemed to come into play around early to mid-1997. Love to hear what others can find/recall.