Googleではログインして利用しているユーザーの全ての検索履歴をGoogleのサーバー上に保管しています。
ここで言う検索履歴とはWeb検索の履歴です。
保存しているのは「何時何分に」何の「検索ワード」をしたのか。
検索した場所情報があれば、「どこで」検索したのか。
検索した結果「どのサイトをクリック」して表示したのか。
が保存されています。
https://history.google.com/history/
2016年5月現在検索履歴が表示できるサイト。
これが保存されるには、
Googleアカウントにログインしている状態である事。
検索履歴を残す設定にしている事。
という条件が必要です。
どちらかが欠けていた場合は、特定個人のデータとしては保存されませんが、1ユーザーのデータとして残り、Googleが内部で利用する事と思われます。
パソコンやスマートフォンで利用する場合は、2016年5月現在、右上にログイン済みのアイコンが表示されていればログインしたことになります。
Androidの場合はGoogleアカウントにログインしている状態が標準状態となります。