Buenas compañero!
Pues yo hace poco tuve que hacer algo parecido en el trabajo y lo que usé para añadir esa columna fue algo parecido a esto:
<asp:GridView runat="server" ID="myGrid" OnRowCommand="controlarRowCommand">
<Columns>
<asp:TemplateField>
<HeaderTemplate>
<asp:CheckBox runat="server" ID="chkSeleccionarTodos" OnCheckedChanged="onSeleccionarTodos" />
</HeaderTemplate>
<ItemTemplate>
<asp:CheckBox runat="server" ID="chkSeleccionarEste" OnCheckedChanged="onSeleccionarEste" />
</ItemTemplate>
</asp:TemplateField>
</Columns>
</asp:GridView>
El elemento que está en el HeaderTemplate es el encargado de marcar o desmarcar todos los elementos...
Si no necesitas el de marcar todos, puedes usar un <asp:CheckBoxField...> con un rowCommand que te será más fácil acceder a todos los datos de la fila.
Si necesitas algo más... Mañana echo un vistazo.
Un saludo!!!