1) Download .iso live CD/DVD for your desired distro
2) Start Parallels
3) Hit the + on Parallels Virtual Machines or click File | New... in the menu
4) Double-click Install Windows from DVD or image file (or highlight Install Windows... and click Continue)
5) Locate your .iso file in the Install from drop down (select Choose an image file... to open a file dialog)
6) Parallels will attempt to 'auto-detect' your OS. If it fails, select from the drop down. More Linux lists popular distros, and you can always choose Other Linux Kernel 2.6 (this works even if your distro uses Linux 3.0.x)
7) Continue with the install
It's not intuitive that it's behind the Install Windows option, but that's where it is.
