Generated CheckBox column reflects the table selection. Selecting a table row set's the checkbox to checked. Deslecting a row sets the checkbox column to unchecked. Toggling the checkbox selects/deselcts the row. A bit ugly, frankly, but it works.

TableCheckBoxUI.java

package uk.org.backstage;

import com.vaadin.annotations.VaadinServletConfiguration;
import com.vaadin.data.Property;
import com.vaadin.data.util.IndexedContainer;
import com.vaadin.server.VaadinRequest;
import com.vaadin.server.VaadinServlet;
import com.vaadin.ui.AbstractSelect;
import com.vaadin.ui.CheckBox;
import com.vaadin.ui.Table;
import com.vaadin.ui.UI;
import com.vaadin.ui.VerticalLayout;

import javax.servlet.annotation.WebServlet;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

@SuppressWarnings("serial")
public class TableCheckBoxUI extends UI {

  private static final String CHECKBOX_COLUMN = "selected";

  /**
   * This map keeps track of all the created and attached checkboxes, by ItemId
   */
  protected Map<Object, CheckBox> itemIdToCheckbox = new HashMap<Object, CheckBox>();

  /**
   * This is the last selection value of the table. We need to keep track of what *was* selected,
   * so that we can "deselect" the checkboxes.
   */
  private Object lastSelectionValue;

  /**
   * A simple flag to stop a circular event
   */
  private boolean ignorePropertyChangeEventInCheckBoxListener;

  @WebServlet(urlPatterns = {"/tablecheckbox/*", "/VAADIN/*"}, asyncSupported = true)
  @VaadinServletConfiguration(productionMode = false, ui = TableCheckBoxUI.class)
  public static class Servlet extends VaadinServlet {
  }

  @Override
  protected void init(VaadinRequest request) {
    IndexedContainer container = createContainer();
    Table table = createTable(container);

    VerticalLayout mainLayout = new VerticalLayout();
    mainLayout.addComponent(table);

    mainLayout.setSizeFull();
    setContent(mainLayout);
  }


  private Table createTable(IndexedContainer container) {
    final Table table = new Table();
    table.setImmediate(true);
    table.setContainerDataSource(container);
    table.setSizeFull();
    table.setColumnExpandRatio("number", 1f);

    table.addGeneratedColumn(CHECKBOX_COLUMN, new Table.ColumnGenerator() {
      @Override
      public Object generateCell(final Table source, final Object itemId, Object columnId) {

        final CheckBox checkBox = new CheckBox("", isItemIdSelected(source, itemId));
        checkBox.addValueChangeListener(new Property.ValueChangeListener() {
          @Override
          public void valueChange(Property.ValueChangeEvent valueChangeEvent) {
            // Don't react to the event if we're being changed from the table-value-change event
            if (!ignorePropertyChangeEventInCheckBoxListener) {
              Boolean selected = (Boolean) valueChangeEvent.getProperty().getValue();
              if (selected) {
                source.select(itemId);
              } else {
                source.unselect(itemId);
              }
            }
          }
        });

        // Let's keep track of the checkboxes
        checkBox.addAttachListener(new AttachListener() {
          @Override
          public void attach(AttachEvent event) {
            itemIdToCheckbox.put(itemId, checkBox);
          }
        });
        checkBox.addDetachListener(new DetachListener() {
          @Override
          public void detach(DetachEvent event) {
            itemIdToCheckbox.remove(itemId);
          }
        });
        return checkBox;
      }
    });

    table.setMultiSelect(true);
    table.setSelectable(true);

    // Let's select a few initial items
    Set<Integer> selectedItems = new HashSet<Integer>();
    selectedItems.add(1);
    selectedItems.add(4);

    table.setValue(selectedItems);

    this.lastSelectionValue = table.getValue();
    this.ignorePropertyChangeEventInCheckBoxListener = false;

    /*
     * When the table value - i.e. the selection - changes, make sure
     * any attached checkboxes are updated
     */
    table.addValueChangeListener(new Property.ValueChangeListener() {
      @Override
      public void valueChange(Property.ValueChangeEvent event) {

        ignorePropertyChangeEventInCheckBoxListener = true;
        Object newSelectionValue = event.getProperty().getValue();
        /* Deselect all of the old checkboxes, then reselect all of the new ones.
          If we wanted to be really smart, you could work out which checkboxes you wanted to change.
          I don't care about being smart right now */
        setCheckBoxes(lastSelectionValue, false);
        setCheckBoxes(newSelectionValue, true);

        lastSelectionValue = newSelectionValue;
        ignorePropertyChangeEventInCheckBoxListener = false;
      }
    });
    /* Just some cosmetics : no caption for the checkbox, and make it the first column */
    table.setColumnHeader(CHECKBOX_COLUMN, "");
    table.setVisibleColumns(CHECKBOX_COLUMN, "name", "number");
    return table;
  }

  /**
   * Set the value of all of the checkboxes
   * @param itemIdOrIds
   * @param value
   */
  private void setCheckBoxes(Object itemIdOrIds, boolean value) {
    if (itemIdOrIds instanceof Collection) {
      Collection ids = (Collection) itemIdOrIds;
      for (Object id : ids) {
        setCheckBox(id, value);
      }
    } else {
      setCheckBox(itemIdOrIds, value);
    }
  }

  /**
   * Set the value of the given checkbox
   * @param id
   * @param value
   */
  private void setCheckBox(Object id, boolean value) {
    CheckBox checkBox = itemIdToCheckbox.get(id);
    if (checkBox != null) {
      checkBox.setValue(value);
    }

  }

  /**
   * Is the given itemId selected ?
   * @param select
   * @param itemId
   * @return
   */
  protected boolean isItemIdSelected(AbstractSelect select, Object itemId) {
    Object value = select.getValue();
    if (itemId == null || value == null) {
      return false;
    }

    if (select.isMultiSelect()) {
      return ((Collection) value).contains(itemId);
    }

    return itemId.equals(value);
  }

  private IndexedContainer createContainer() {
    IndexedContainer container = new IndexedContainer();
    container.addContainerProperty("name", String.class, null);
    container.addContainerProperty("number", Integer.class, null);

    // Generate lots of rows, to check performance isn't too bad
    for (int i = 0; i < 1000; i++) {
      addItem(container, "Bob", 10);
      addItem(container, "Harry", 1);
      addItem(container, "Margaret", 0);
      addItem(container, "Glenda", 22);
      addItem(container, "Boris", 0);
      addItem(container, "Jessica", 24);
    }

    return container;
  }


  private void addItem(IndexedContainer container, String name, int number) {
    Object itemId = container.addItem();
    container.getItem(itemId).getItemProperty("name").setValue(name);
    container.getItem(itemId).getItemProperty("number").setValue(number);
  }

}

I solved this by removing the detatch listener but keeping the attach listener and adding: (Note the cast depends on your table's underlying datasource...May not be available for all.)

        // This handles removing the checkbox we're tracking when an item is removed.
        ((BeanItemContainer<?>)table.getContainerDataSource()).addItemSetChangeListener(new ItemSetChangeListener() {
            private static final long serialVersionUID = 1L;
            @Override
            public void containerItemSetChange(ItemSetChangeEvent event) {
               Collection<?> existing = event.getContainer().getItemIds();
               Iterator<?> it = itemIdToCheckbox.keySet().iterator();
               while(it.hasNext()) {
                  Object key = it.next();
                  if(!existing.contains(key)) {
                      it.remove();
                  }
               }
            }
        });