Do parallel lines have to be on the same plane?

Yes. Parallel means they they are always the same distance and they never intersect, and this could only mean on the same plane. However, the proof that it works is a little harder than one might think.