CSS solution
If you can work with background images here, the easiest and most efficient solution would be CSS based.
Take a look at /com/google/gwt/user/cellview/client/CellTree.css (in gwt-user.jar). There you see the css classes ".cellTreeItem" and ".cellTreeSelectedItem". The latter one already has an image. You could assign it your own, and for ".cellTreeItem" a different one.
For general information how to adjust CellTable/CellTree/... styles, see e.g. https://stackoverflow.com/a/6387210/291741
Cell solution
You could construct your cell with the SelectionModel like
public MyCell(SelectionModel selectionModel) {
this.selectionModel = selectionModel;
}
public void render(final Cell.Context context, final Node value,
final SafeHtmlBuilder sb) {
if (selectionModel.isSelected(...
}
However, you will probably need to retrigger the cell rendering when the selection changes. It's probably possible, but I've never done that.