This is a tree with two columns, the first of which is a checkbox. I followed information from the XUL treecol docs to specify the first column as a checkbox:
http://developer.mozilla.org/en/docs/XUL:Attribute:treecol.type

I am able to display a checkbox and change its state. I still have some problems:

1. (Mozilla Bug 312457)I don't hear the state of the checkbox with JAWS, and I don't see anything through MSAA to indicate that there is a checkbox.
   
   It appears as though Mozilla is collecting up the entire row as a single MSAA item and missing the presence of the checkbox - WAI roles don't seem to work either (used in this example).
2. How do you specify one of these checkboxes as disabled? In the example, Label One is just a category and not a selectable item. I found docs that imply there is CSS for a disabled state, so I could set the disabled set for these categories and have no image, but I haven't figured out how to trigger this state yet.
3. If the first element is selected, double clicking the second checkbox collapses the first element.