First I add TVS_EX_PARTIALCHECKBOXES to the CTreeCtrl's extended styles:
TreeView_SetExtendedStyle(tree->GetSafeHwnd(), TVS_EX_PARTIALCHECKBOXES, TVS_EX_PARTIALCHECKBOXES);
Now how do I actually set any item to this state? There doesn't appear to be any documentation about that. I guessed that since checking and unchecking works by changing the item's state image to 1 or 2, I can try my luck with 3:
tree->SetItemState(tree->GetFirstVisibleItem(), INDEXTOSTATEIMAGEMASK(3), TVIS_STATEIMAGEMASK);
Of course that would have been too easy, it just made the image disappear.