I thought of drag and drop because that's how the old widget area used to work in 2.4, and I always thought it was a great metaphor. On one side, here's all your stuff, and on another side, here's the stuff you've put on the page. Best of all, each list was mutually exclusive, so you couldn't choose a widget twice.
That solution, or one like it, would resolve two inherent limitations of checkboxes:
1) You can see immediately which records are included without thumbing through the grid
2) You avoid using a metaphor that has ambiguous meaning. In the rest of the world, checkboxes in a table are used to queue up a bulk action (e.g. Gmail). When bulk deletes become available for GridField, it will create a confusing UI.
I think at the very least the checkbox column should be labeled so that users know what the checkbox is for. It should also be clear that the user has to save the page to persist the checkboxes, because again, checkboxes on a table are not conventionally a saveable entity. Some kind of feedback when you check the box might help, such as adding the record to a separate list, like my WidgetArea example.
Maybe something more like an on/off switch. Something that stands out as different than the checkboxes used for tabular bulk actions. All I know is, I've implemented dozens of ManyManyDOMs in the last few years, and I've never had a client who didn't need it explained to him or her, and didn't subsequently need it explained again down the road.
It's a tricky thing to articulate in a UI. I think I know now why SS avoided implementing it in 3.0.