  The nominal mission maps from the Planck satellite contain a wealth of
information about secondary anisotropies in the cosmic microwave background
(CMB), including those induced by the thermal Sunyaev-Zel'dovich (tSZ) effect
and gravitational lensing. As both the tSZ and CMB lensing signals trace the
large-scale matter density field, the anisotropies sourced by these processes
are expected to be correlated. We report the first detection of this
cross-correlation signal, which we measure at 6.2 sigma significance using the
Planck data. We take advantage of Planck's multifrequency coverage to construct
a tSZ map using internal linear combination techniques, which we subsequently
cross-correlate with the publicly-released Planck CMB lensing potential map.
[Abridged] We interpret the signal using halo model calculations, which
indicate that the tSZ -- CMB lensing cross-correlation is a unique probe of the
physics of intracluster gas in high-redshift, low-mass groups and clusters. Our
results are consistent with extrapolations of existing gas physics models to
this previously unexplored regime and show clear evidence for contributions
from both the one- and two-halo terms, but no statistically significant
evidence for contributions from diffuse, unbound gas outside of collapsed
halos. We also show that the amplitude of the signal depends rather sensitively
on the amplitude of fluctuations ($\sigma_8$) and the matter density
($\Omega_m$). We constrain the degenerate combination $\sigma_8
(\Omega_m/0.282)^{0.26} = 0.824 \pm 0.029$, a result that is in less tension
with primordial CMB constraints than some recent tSZ analyses. Our detection is
a direct confirmation that hot, ionized gas traces the dark matter distribution
over a wide range of scales in the universe ($\sim 0.1$--$50 \, {\rm Mpc}/h$).
