Gmailについての質問です。Gmailがツリーになるかどうかは、件名が同じかどうかで判断されているのでしょうか？

gmailに限りませんが大抵のメーラーはRFCに従っているはずです。
http://labs.opentone.co.jp/?p=5654
http://www.emaillab.org/essay/message-id.html
上記リンク先にもありますが、件名でのハンドリングもしているようです。

Google と契約を結んでるっぽい会社のサポートフォーラムの FAQ から。

なお、Gmail では多数の要素を考慮してメールをスレッドに分類しているため、上記以外の挙動となる場合もございますので予めご了承ください。
公開可能な情報につきましては以下のヘルプ記事のみとなり、詳細な判定基準などのアルゴリズムにつきましては情報を公開しておりません。

メールがスレッドになる条件を教えてください。 : クラウド コンシェルジュ

確かに、Google の公式ページでは見つかりません。

Wikipedia の Gmail の項。

スレッドビュー
Gmail の特徴のひとつであるメールの表示方法。メールとそれへの返信メールを1つの「スレッド」としてまとめ、メールごとではなくスレッドごとに表示する。それぞれのスレッドを開くとメールでの会話がカードを重ねるように表示され、新着のメールは、カードが展開された状態になって、本文が表示される。通常のメーラとは異なり、ヘッダ内の References: 行や In-Reply-To: 行以外に、Subject: 行とFrom: 行も参照しており、同一送信者から来た同一サブジェクトの新規スレッドメールは、1つのスレッドにまとめられる。1つのスレッド内のメール数が100通を超えると、新しいスレッドに分割される。2010年9月29日にはスレッド表示をオフにする機能が追加された[8]。

Gmail - Wikipedia

ふうん、って感じですが、書いてある通りにはなっていないです（後述）。
それに、脚注で示されている情報ソースには、そんなことはちっとも書かれてません。

後、スレッドにまとめることとは直接関係ありませんが、Gmail がメールのヘッダをいろいろ見ているらしいという一面。

Gmailの内部実装がどうなっているのかはもちろん不明なので、 あくまで下記は私自身がGmailの挙動を見ての推測でしかないことはあらかじめ断わっておくが、 どうやらGmailはヘッダの Message-Id を元に同一メールかどうかを判定しているようだ。 そして、問題は、既に同じ Message-Id のメールを所持していると、 後から受け取った同じ Message-Id のメールは破棄されるらしいことだ。

まあ、どういうことなのかはなんとなく想像はできる。要は多分、Message-IdをKeyにしてメールを管理しているのだ。そして重複があれば上書ではなく後から来たものを破棄する。Message-Idのフィールドの意味を考えれば、別段不思議な実装でもないように思う。思うが...

Gmailでメーリングリストに投稿したはずのメールが受け取れない？ - TIM Labs

ぼくがはてなで使ってる gmail の様子です。

• はてなスターのレポートは、毎日同じタイトルで送信されてくる（送信者が同じなのは当然）が、スレッドとしてまとめられない
  → Wikipedia の記述と違う
• 人力検索の回答にコメントが付いた場合にも、まとめられたり、まとめられなかったり（これも、送信者がry
  → 同じ質問だからひとつにまとめられている、ということはないです。これも、Wikipedia の記述と違う
• スクリーンショットでは分かりませんが、特定の相手と返信、返信とやったメールはひとつのスレッドにまとめられる

こういった辺りから、以下のような判定ロジックになっているのではないかと推測します。

• メールヘッダの References: と In-Reply-To: が同じものは、ひとつのスレッドにする
  → 普通のメーラーと同じで、特定の相手とのメールのやり取りが、ひとつのスレッドにまとめられるのはこれ。　　（どうやら違うようです →追記）
• ほぼ同じタイトル（Re: や Fwd: などは無視される）で、送信者と送信日が同じ日のメールはひとつのスレッドにする
  → 回答のコメントがまとめられたり、そうじゃなかったり、というのはこれ。同じタイトルで送信者が違う場合については、実験してみました。

• メールに返信（In-Reply-To: が正しく設定されてる）でも、タイトルを変えると別のスレッドになる
• 新規にメールを発信した場合、タイトルが同じなら同じスレッドになる
• 新規にメールを発信で、タイトルに Re: や Fwd: をつける（タイトルだけ、返信や転送に偽装）と同じスレッドになる

どうやら、メールヘッダを当てにせず、タイトルだけでまとめる／まとめないを決めている様子です。

普段 来ている、はてなからの通知（☆レポートや回答のコメント）では、一日経つと別のスレッドになるようなので、

• タイトルがほぼ同じ（Re: や Fwd: は無視）だと、同じスレッドにする
• 日が変わると、別のスレッドになる

という感じのようです。