In the meaningful sequences of genes, each codon is uncorrelated with other codons, which means it looks like white noise, or essentially a random sequence. To convey the highest amount of information in the smallest amount of space, each piece of information should be orthogonal. This would appear no different than a random sequence. Dropping information, if there is proof reading, should not automatically result in a loss. But let us assume data is added instead. A mutuation increases the information. For it to actually increase information, the added codons must be uncorrelated with the other codons. If they were correlated, then some or all of the information would already be in the other codons.
So let us assume it is uncorrelated, essentially white noise. There are three possibilities for this white noise. First, it really could be meaningless noise, in which case the codons exist but do not code any protein. This is no different than if the mutuation did not exist. Second, it could code a deletarious protein and either kill the organism or make the reproductive line less successful, essentially committing genetic suicide by selection. Third, the random sequence could be useful, in which case, it would add information and if it led to increased reproductive success in the line, would become a permanent feature of the species or even cause a new species under certain circumstances.
You can see the association between randomness and information. Correlation implies the information already exists and therefore the information is wasteful. Only uncorrelated information is efficient. Uncorrelated information looks like Gaussian white noise. Since chemical mutations are essentially Gaussian white noise triggered by the Second Law of Thermodynamics, the only way valuable change can happen is through chance events. The selection process then skews the distribution so that even though most mutations are not helpful, the helpful have a statistical survival advantage that makes it more likely to propogate.