We construct the lattice gauge theory of the group G_N, the semidirect product of the permutation group S_N with U(1)^N, on an arbitrary Riemann surface. This theory describes the branched coverings of a two-dimensional target surface by strings carrying a U(1) gauge field on the world sheet. These are the non-supersymmetric Matrix Strings that arise in the unitary gauge quantization of a generalized two-dimensional Yang-Mills theory. By classifying the irreducible representations of G_N, we give the most general formulation of the lattice gauge theory of G_N, which includes arbitrary branching points on the world sheet and describes the splitting and joining of strings.