We have developed a method to identify planetary nebula (PN) candidates in imaging data of the Sloan Digital Sky Survey (SDSS). This method exploits the SDSS's five-band sampling of emission lines in PN spectra, which results in a color signature distinct from that of other sources. Selection criteria based on this signature can be applied to nearby galaxies in which PNe appear as point sources. We applied these criteria to the whole area of M31 as scanned by the SDSS, selecting 167 PN candidates that are located in the outer regions of M31. The spectra of 80 selected candidates were then observed with the 2.2 m telescope at Calar Alto Observatory. These observations and cross-checks with literature data show that our method has a selection rate efficiency of about 90%, but the efficiency is different for the different groups of PN candidates. In the outer regions of M31, PNe trace different well-known morphological features like the Northern Spur, the NGC 205 Loop, the G1 Clump, etc. In general, the distribution of PNe in the outer region 8 < R < 20 kpc along the minor axis shows the "extended disk" - a rotationally supported low surface brightness structure with an exponential scale length of 3.21 ± 0.14 kpc and a total mass of ∼1010 M, which is equivalent to the mass of M33. We report the discovery of three PN candidates with projected locations in the center of Andromeda NE, a very low surface brightness giant stellar structure in the outer halo of M31. Two of the PNe were spectroscopically confirmed as genuine PNe. These two PNe are located at projected distances along the major axis of ∼48 Kpc and ∼41 Kpc from the center of M31 and are the most distant PNe in M31 found up to now. With the new PN data at hand we see the obvious kinematic connection between the continuation of the Giant Stream and the Northern Spur. We suggest that 20%-30% of the stars in the Northern Spur area may belong to the Giant Stream. In our data we also see a possible kinematic connection between the Giant Stream and PNe in Andromeda NE, suggesting that Andromeda NE could be the core or remnant of the Giant Stream. Using PN data we estimate the total mass of the Giant Stream progenitor to be ≈109 M. About 90% of its stars appear to have been lost during the interaction with M31.