There are a couple of ways you can think of this. The best way is to understand that when heat is given off to the environment, the conditions within the chemical system have changed. The system itself becomes more random because the energy that kept in place is disappearing with the energy given up to the surroundings.
To picture this statement, imagine you have a cube containing two chemicals that when they react, will make heat. Draw a diagram with nine dots in the upper left corner. The reaction takes place. Now draw another diagram where there are arrows leading away from the cube's face.
Add nine dots all over the face of the cube. That represents an increase in entropy. It becomes more random.