例えば、グーグルで「はてな」と検索すると、関連検索という形で、「はてなダイアリー」や「はてなブックマーク」などが出てきます。

サイトリンクですね。

http://www.google.co.jp/support/webmasters/bin/answer.py?answer=...

現時点では、サイトリンクは完全に自動化されています。Google ではサイトリンクのアルゴリズムを改善できるよう常に努力しており、将来は、ウェブマスターによる入力を取り入れる可能性もあります。

との事なので、「どのくらいの期間に２キーワードを何回検索する人がいたら、関連検索として表示される」、などと言った決まりがあるかもしれませんが、非公開とされているようですね。

http://web-tan.forum.impressrd.jp/e/2007/12/10/2314

こちらでは、サイトリンク表示獲得に影響を及ぼす可能性のある要素として以下の物を上げています。

ドメイン名の権威と信頼性（主にリンクと、おそらくはなんらかの運営年数的要素を基準にしたもの）。

ブランド名検索クエリの量。

高いページランクを複数獲得しているか否か。内部ページに対する検索が数多く行われているか否か。

相当量のドメイン名トラフィックがあるかどうか（ツールバーユーザーなどのデータを通じて計測したもの）。

ウェブに存在するページ全体における、ブランドやドメイン名への言及の数。

リンクの増加傾向（該当サイトに対するリンクが、常時増えているか、あるいは突発的で定常性のない増え方をしているか）。

Yahoo!とGoogleで異なる「関連検索キーワード」表示の仕組み | Web担当者Forum

エッセンシャル・サーチエンジン: GoogleとYahoo!の関連検索

Googleはyahoo!と違ってクロールベースで

関連検索を表示するようです。

つまり、ユーザーが何と何を同時検索したのかではなく、

Googleの検索ロボットがネットをクロールした時に

同時に出現した頻度の高い語句を表示します。

ですから、

検索ロボットが「はてな」という語句でネットをクロールした時に

同サイト上に「人力検索」という語句が掲載されている頻度が高ければ

関連検索用語としてピックアップされます。

誰が何を検索したかには全く関係ありません。

グーグル、「関連検索」のデータを更新 :: SEM R

そして関連検索キーワードはリアルタイムに更新されるのではなく

一定期間ごとに更新されるようです。

こちらの記事をみる限りでは

更新されたかどうかは、検索してみなければわからないようです。