We have detected stellar halo streams in the solar neighborhood using data from the seventh public data release of the Sloan Digital Sky Survey (SDSS), which includes the directed stellar program Sloan Extension For Galactic Understanding and Exploration (SEGUE). In order to derive distances to each star, we used the metallicity-dependent photometric parallax relation from Ivezić et al. We examine and quantify the accuracy of this relation by applying it to a set of globular and open clusters observed by the SDSS/SEGUE and comparing the resulting sequence to the fiducial cluster sequences obtained by An et al. Our final sample consists of 22,321 nearby (d <= 2 kpc), metal-poor ([Fe/H] <=-0.5) main-sequence stars with six-dimensional estimates of position and space velocity (vec{r},vec{v}). We characterize the orbits of these stars through suitable kinematic proxies for their "effective" integrals of motion, angular momentum, eccentricity, and orbital polar angle and compare the observed distribution to expectations from a smooth distribution in four [Fe/H] bins. The metallicities provide an additional dimension in parameter space that is well suited to distinguish tidal streams from those of dynamical origin. On this basis, we identify at least five significant "phase-space overdensities" of stars on very similar orbits in the solar neighborhood to which we can assign unambiguously peaked [Fe/H] distributions. Three of them have been identified previously, including the halo stream discovered by Helmi et al. at a significance level of σ = 12.0. In addition, we find at least two new genuine halo streams, judged by their kinematics and [Fe/H], at σ = 2.9 and 4.8, respectively. For one stream the stars even show coherence in the configuration space, matching a spatial overdensity of stars found by Juric et al. at (R, z) ≈ (9.5, 0.8) kpc. Our results demonstrate the practical power of our search method to detect substructure in the phase-space distribution of nearby stars without making a priori assumptions about the detailed form of the gravitational potential.