According to a new tool by Google called Google Correlate, you can look back at a lot of data. So, I decided to search Google Correlate for Search Engine Optimization.
Apparently on June 12, 2005, it was a historic day of epic proportions: more people searched for search engine optimization on that day than on any day in history.