We reconstruct the gravitational lensing convergence signal from Cosmic Microwave Background (CMB) polarization data taken by the POLARBEAR experiment and cross-correlate it with Cosmic Infrared Background (CIB) maps from the Herschel satellite. From the cross-spectra, we obtain evidence for gravitational lensing of the CMB polarization at a statistical significance of 4.0$sigma$ and evidence for the presence of a lensing $B$-mode signal at a significance of 2.3$sigma$. We demonstrate that our results are not biased by instrumental and astrophysical systematic errors by performing null-tests, checks with simulated and real data, and analytical calculations. This measurement of polarization lensing, made via the robust cross-correlation channel, not only reinforces POLARBEAR auto-correlation measurements, but also represents one of the early steps towards establishing CMB polarization lensing as a powerful new probe of cosmology and astrophysics.