Yes, the Nat Semi app note method requires two channels. If the temperature is above "0" then the output will be above the GND terminal of the LM34, if the temperature is below "0", then the the output will be below the GND terminal of the LM34, but both of them will be positive with respect to PIC GND.
Read both channels. Subtract the smaller reading from the larger and compute the temp. If the channel 1 reading is larger than the channel 2 reading the temp is positive. Otherwise the temp is negative.

Another way that takes only one channel: Replace the two diodes shown in the application note with a 1.25V precision reference. Since you now know that the GND terminal of the LM34 is at 1.25V, "0" degrees will give you 1.25V into the A/D. -20 degrees will give you 1.05V (1.25V - (10mv/degree * 20 degrees)).