Yes, we do need to expose a way to set the icons (and other appearance details) for the Tree in the TreeGrid on an individual basis, but the theming setup still works - you can still configure the entire application's theme to have a specific appearance impl.
The interface com.sencha.gxt.widget.core.client.tree.Tree.TreeAppearance gets its implementation from these lines in com/sencha/gxt/theme/blue/Blue.gwt.xml:
indicating that the class com.sencha.gxt.theme.blue.client.tree.BlueTreeAppearance should be used whenever GWT.create(TreeAppearance.class) is called.
<when-type-is class="com.sencha.gxt.widget.core.client.tree.Tree.TreeAppearance" />
You can add these lines to your own module to point to your own appearance implementation.
We'll update this bug when there is a way to set the specific tree appearance info for the TreeGrid, but in general, you'll want to use this other way, to build your own application specific themes.