Buenas, debes poner el código en el evento CellContentClick:
Código:
Private Sub dataGridView1_CellContentClick(ByVal sender As Object, ByVal e As DataGridViewCellEventArgs) Handles dataGridView1.CellContentClick
If e.ColumnIndex = 0 AndAlso Not dataGridView1.Rows(e.RowIndex).IsNewRow Then
Label1.Text = "Has seleccionado la linea " & e.RowIndex
End If
End Sub
Saludos