保存した情報をどう使うか、と言うことにも依りますのでいくつかの方法があります。
例えば、Cookieに保存しただけですと、サーバー側でその履歴を集計してマーケティングに役立てたいとなった場合、Cookieはユーザーのクライアントに保存される情報ですので、サーバー側で集計することは困難となります。
逆に、単にユーザビリティの向上のために、クライアント側で検索履歴を出してあげたいという用途でしたら、Cookieを使うだけでも十分でしょう。
但し、例えばユーザーログインなどがあるサイトの場合に、ユーザーが複数のブラウザ(PCとスマホ)などでログインしたとしても、Cookieだとブラウザ単位での保存になるので、情報を使いまわすことができません。
こういったことを解決し、例えば広告に使うとかの用途があるのでしたら、サーバー側で保存する事になります。
その際の保存先はデータベースやNoSQLなどが一般的になるかと思います。
なお、Cookieは容量の制限があるため、大量のデータを保存するのには向きません。
シリアライズした情報をそのままCookieに突っ込むより、PHPでしたらSessionを使ったり、最近のブラウザでしたらローカルストレージなども使った方が制約が減るので楽にはなると思います。
このように、一般的にと言っても要件によって解決策は様々になります。
初学者であるのなら、とりあえず出来そうな方法で作ってみて、その上でメリットやデメリットを体感してみるのも良いかと思います。