Это не один вопрос, а два, притом ответ на каждый тянет на полноценный томик страниц на 300-500. Но если очень сильно обобщить и упростить, то появление гипертекста было предсказано ещё в 40-х годах прошлого века, а реализовано было в 70-х. Где-то там и стоит искать самые истоки.
Суть в том, что изначально поисковых систем в их нынешнем виде не существовало: были сайты-каталоги, подобные всё ещё живым Yahoo!, Rambler или тем структурам, что используются в Tor для поиска информации. Пользователь заходит на такой сайт, ищет заданный раздел, и уже оттуда переходит на целевую страничку.
Прототипы поисковых систем появились изначально в локальных сетях (чаще всего - университетских) и в больших библиотеках для поиска документов. И только в 90-е появились полноценные поисковые системы (та же AltaVista) как альтернатива каталогам.
Причина же появления SEO была до крайности проста: речь идёт о спаме и рекламных объявлениях. Бизнесмены быстро поняли, что люди не обращаются к поисковикам и каталогам ради абстрактной информации. А значит, нужно показать им соответствующее коммерческое предложение. И чтобы показать таких предложений больше, нужно быть в выдаче повыше. И SEO в таких вопросах стало одним из каналов наряду с платной рекламой и баннерами. И изначально SEO развивалось как разновидность спама и манипуляций недочётами поисковых систем.
В какой-то мере, SEO сохраняет такой характер и сегодня. Однако к принципам информационного поиска и манипуляциями уязвимостями алгоритмов теперь это ещё и поисковый маркетинг, а также ещё несколько исключительно маркетинговых дисциплин и средств того же PR.
Но это уже совсем другая история.