We demonstrate photonic crystal nanobeam cavities that support both TE- and TM-polarized modes, each with a Quality factor greater than one million and a mode volume on the order of the cubic wavelength. We show that these orthogonally polarized modes have a tunable frequency separation and a high nonlinear spatial overlap. We expect these cavities to have a variety of applications in resonance-enhanced nonlinear optics.