Using Planck maps of six regions of low Galactic dust emission with a total area of about 140 square degrees, we determine the angular power spectra of cosmic infrared background (CIB) anisotropies from multipole l = 200 to l = 2000 at 217, 353, 545 and 857 GHz. We use 21-cm observations of HI as a tracer of thermal dust emission to reduce the already low level of Galactic dust emission and use the 143 GHz Planck maps in these fields to clean out cosmic microwave background anisotropies. Both of these cleaning processes are necessary to avoid significant contamination of the CIB signal. We measure correlated CIB structure across frequencies. As expected, the correlation decreases with increasing frequency separation, because the contribution of high-redshift galaxies to CIB anisotropies increases with wavelengths. We find no significant difference between the frequency spectrum of the CIB anisotropies and the CIB mean, with Delta I/I=15% from 217 to 857 GHz. In terms of clustering properties, the Planck data alone rule out the linear scale- and redshift-independent bias model. Non-linear corrections are significant. Consequently, we develop an alternative model that couples a dusty galaxy, parametric evolution model with a simple halo-model approach. It provides an excellent fit to the measured anisotropy angular power spectra and suggests that a different halo occupation distribution is required at each frequency, which is consistent with our expectation that each frequency is dominated by contributions from different redshifts. In our best-fit model, half of the anisotropy power at l=2000 comes from redshifts z<0.8 at 857 GHz and z<1.5 at 545 GHz, while about 90% come from redshifts z>2 at 353 and 217 GHz, respectively.