「アイテムがチェックされた／チェック解除された」という通知は無いようですので、
NM_CLICK を受けて処理することになるかと思います。
NM_CLICK では、どのアイテムがチェックされたかわかりませんが、チェック状態が変化
したとき、マウスカーソルはチェックボックスの上にあるはずです。
このチェックボックスは、ツリービューの「状態イメージ」という形で存在しています
ので、TVM_HITTEST メッセージを送ってみて、マウスカーソルが状態イメージの上にあ
れば、チェック状態が変化したと判断できると思います。
あとは、
・チェックが解除されていれば、全ての子アイテムのチェックを解除する
・兄弟アイテム全てにチェックがついていれば、親アイテムにチェックをつける
というところは難しくないと思います。

また、アイテムを選択して Space キーを押したときもチェック状態が変化するようで
す。
これは TVN_KEYDOWN 通知を捕まえればできると思います。
この時は、チェック状態が変化したアイテムは選択状態にあるはずですので、ヒットテ
ストは要りません。

肝心なことを書いていなかった。

アイテムがチェックされているかどうかをチェックするには、以下のようなコードを使
います。
なお、hTreeView はツリービューコントロールのウィンドウハンドル、hItem はチェッ
ク状態が変化したアイテムのハンドルです。

TVITEM tvi;
tvi.mask = TVIF_HANDLE | TVIF_STATE;
tvi.hItem = hItem;
tvi.stateMask = TVIS_STATEIMAGEMASK;

if( SendMessage( hTreeView, TVM_GETITEM, 0, ( LPARAM )&tvi ) )
{
BOOL bChecked =
( ( ( tvi.state & TVIS_STATEIMAGEMASK ) >> 12 ) == 2 );
}

が、どういうわけか、チェック状態の取得がうまくいきませんでした。ごめんなさい。
NM_CLICK を捕まえた時点では、まだチェック状態が反映されてなく、bChecked が意図
したのとは逆の値になってしまうようです（チェックされていれば 0、そうでなければ
1）。
この件に関する情報をお持ちの方がいらっしゃいましたら、フォローお願いできますで
しょうか。

シャノンさんが言われている通り、NM_CLICKは結果反映前の状態みたいですね。
見たところ、

TVM_HITTEST メッセージを送ってみて、マウスカーソルが状態イメージの上にあ
れば、チェック状態が変化したと判断できると思います。

というのは確かにそうなっているので取り出した状態を反転させるような判断でも
いけそうな気がします。
そうでなければ、ツリービューに対応した情報の配列それぞれにチェックボックスに
対応したフラグを設けておいてそれで判断するとか。
挙動が決まっているのであれば、それで何とかなりそうです。
どうも、ツリーコントロールのチェックボックスはリアルタイムに状態を取得する
ような用途を想定していないみたいですね。
多分、ボタンの押下のタイミングでその時の状態を収集して処理するような形態しか
考えられていないみたいです。

TVM_HITTESTを使う以外の方法として参考までに。

NM_CLICKではチェック状態が更新されていませんが
その直後のNM_CUSTOMDRAWではチェック状態が更新されている模様です。
TVN_KEYDOWNの直後にもNM_CUSTOMDRAWが飛ぶようです。

これにひっかければTreeView_GetCheckStateを全アイテムに対して呼び出して
前のチェック状態と比較することで実現できそうな気がします。
ただし、NM_CUSTOMDRAW自身はTreeViewの再描画時にも飛んでくるので気をつけてくださ
い。

その場合はアイテムのパラメータにチェック状態を保持して、
TreeView_GetNextItemで総なめしながらTreeView_GetCheckStateや
TreeView_GetItemを併用してチェックするってのが一番楽っぽい気がします。

# TreeView_XXXX系のものはcommctrl.hにマクロとして定義されています。