To summarize:
You don't have to deinterlace if your final encode is a DVD to be watched on a TV. But if your source is frame based, i.e. originally shot to film not video, then it is preferable.
If you want to watch on a PC, then you should deinterlace. However, deinterlacing truly interlaced material such as that from a DV cam may reduce quality.