The fact that natural processes can — and do — produce new information is a direct consequence of the Second Law of Thermodynamics. This is because information and entropy are one and the same concept.
This was discussed at some length in the thread Information = Entropy.