Windows 8 では、パソコン内のファイルは検索チャームで検索します。
Windows 7 の [スタート] メニューの検索ボックスに代わる機能がこの検索チャームです。
●Windows 8でパソコン内に保存されているファイルを検索する方法
●検索する方法
検索チャームを使って、Web の検索ができます。また PC と SkyDrive 上のアプリ、設定、ファイルを検索できます。
検索 チャームは Windows 7 または Windows Vista の [スタート] メニューの検索ボックスに代わる機能で、デスクトップ画面、スタート画面共通のメニューです。
8から8.1に変えたときにClassic Shellの使用をやめたので試せませんが。
http://www.forest.impress.co.jp/library/software/classicshell/
このURLの先の画像に検索が出ているので
設定の問題だと思います。
7のメニューでなくてXPのメニューになっているとかでは?