Есть несколько предположений:
Замена первой буквы на Я в слове Index - тут можно порассуждать, что I это Я, что было классно указать какую-нибудь букву, написание которой встречается только в кириллице.
Что это сокращение от "языковой индекс"
Мне лично нравится такая версия, что Яндекс так называется, потому что yandex. В новых словах в английском языке, особенно в сокращениях, начинающихся на "ya", можно предполагать, что это сокращение от "yet another" - "а вот ещё один". Такая традиция названий водилась у программистов тех времён. Поэтому это сокращение от "yet another index" - "ещё один индекс". Процесс обработки текстов для быстрого поиска называется индексация, отсюда слово индекс.
Как именно появилось название широкой публике достоверно неизвестно.