Amazon Machine Images (AMIs) have a virtualization type of "HVM" or "PV." What is the difference and which should...
Paravirtualization is a lightweight form of virtualization which differs from HVM in that it doesn't require any virtualization extensions from the host CPU. If your host server doesn't have Intel VT or AMD-V hardware extensions, then you'll need your guest to be paravirtualized.
PV does, however require that a guest OS has a "Xen-PV-enabled kernel" as well as PV drivers, meaning that the guests know that they are running in a hypervisor.
HVM guests are fully virtualized, so the underlying hardware has to be emulated for the guests to use, incurring performance cost, unlike PV, where the guest OS is modified to be able to run without needing that emulation.
If none of this is making sense so far, let me simplify; HVM requires the host machine to have a certain feature present in its hardware, whereas PV requires the guest OS to have a certain feature present in its software.
In practical terms, PV means that performance is much closer to what you would expect of the underlying hardware compared to HVM because of the extra overheads in HVM. As the Xen wiki says: "Fully virtualized guests are usually slower than paravirtualized guests, because of the required emulation."
The answer is simple, then: Choose PV instances because of the better performance. Right? Well, mostly. Since PV requires software changes, it is not possible to run a paravirtualized Windows guest.
The actual answer is nearly simple, then: If you need Windows, you'll need HVM. If you are using GNU Linux or Unix, you can choose either, but will (in most cases) get better performance with PV. The only caveat to make is that HVM isn't supported for t1.micro GNU/Linux instances.
For further reading, there's a good overview of these different types of guests in the Xen wiki.