Этимологический словарь Крылова
гадать
Образовано от той же основы, что и существительное гадь (в настоящее время существует только в диалектах) – "знахарь, прорицатель". Основа эта имеет индоевропейское происхождение (например, в древнеисландском находим geta – "предположение", в готском bigitan – "находить").