We analyze the regularity of random entropy solutions to scalar hyperbolic conservation laws with random initial data. We prove regularity theorems for statistics of random entropy solutions like expectation, variance, space-time correlation functions and polynomial moments such as gPC coefficients. We show how regularity of such moments (statistical and polynomial chaos) of random entropy solutions depends on the regularity of the distribution law of the random shock location of the initial data. Sufficient conditions on the law of the initial data for moments of the random entropy solution to be piece-wise smooth functions of space and time are identified, even in cases where path-wise random entropy solutions are discontinuous almost surely. We extrapolate the results to hyperbolic systems of conservation laws in one space dimension. We then exhibit a class of stochastic Galerkin discretizations which allows to derive closed deterministic systems of hyperbolic conservation laws for the coefficients in truncated polynomial chaos expansions of the random entropy solution. Based on the regularity theory developed here, we show that depending on the smoothness of the law of the initial data, arbitrarily high convergence rates are possible for the computation of coefficients in gPC approximations of random entropy solutions for Riemann problems with random shock location by combined Stochastic Galerkin Finite Volume schemes.