When do I have to use PAE/NX?
You'll need PAE if you are virtualising a 32-bit OS and need more than 4GB of memory.
The comment by @gronostaj and the answer by @ajostergaard both talk only about the Physical Address Extension (PAE) part of PAE/NX. These are both excellent, and I only have clarification to add - the "why" of things. I'll also discuss the "NX" part.
My Answer1
Perhaps a more complete answer, extending the answer of @ajostergaard, would be:
You'll need PAE/NX if you are setting up a virtual, 32-bit OS and:
1) you need more than 4 GiB of memory (RAM)
OR
2) you need to be able to make it so parts of memory cannot be used for executable code, e.g. if you have security concerns which include such attacks as the one described in the NX-bit Wikipedia page (archived),
[C]ertain types of malicious software [can take] over computers by inserting their code into another program's data storage area and running their own code from within this section...
Also, as far as I know, you won't need this PAE/NX option when setting up any 64-bit OS as a virtual machine. (Note, I've only used Intel and AMD CPUs - PAE/NX might be necessary with other processors. MAKE SURE YOU CHECK!)
Further down, I'll describe what the NX part of PAE/NX means and how it relates to security concerns.
(Basically, I was looking for the complete answer. Google brought me here, but I got hung up on the "NX" part. I hope my findings will help others.)
Comments on PAE
It can be hard to get from the the first paragraph in the PAE wiki page (archived) to @ajostergaard's answer. The first paragraph is:
In computing, Physical Address Extension (PAE), sometimes referred to as Page Address Extension, is a memory management feature for the x86 architecture. PAE was first introduced by Intel in the Pentium Pro, and later by AMD in the Athlon processor. It defines a page table hierarchy of three levels (instead of two), with table entries of 64 bits each instead of 32, allowing these CPUs to directly access a physical address space larger than 4 gigabytes (232 bytes).
What?! How does that help us know whether or not to click the checkbox next to "Enable PAE/NX"? Luckily, @ajostergaard told us.
You'll need PAE if you are virtualising a 32-bit OS and need more than 4GB of memory.
So, if your virtual OS is of a 32-bit type (as is the case when you want a virtual Windows-NT OS,) but you have 16GB of RAM (all of which you want to use,) you need the PAE option.
Why? Let me expand on this. You'll need to know that a memory address (archived) is a label for a part of memory - usually for one byte of memory. A 32-bit (4-byte) OS is one which has labels that can go from
zero (0) -- represented in binary by 32 zeros, represented in hexadecimal by 0x 00 00 00 00 --
to
4 294 967 295 -- binary: 32 ones, hexadecimal: 0x FF FF FF FF.
In other words, we have just under 4.3 billion memory addresses, each of which points to one byte of information - to one byte of memory. The point is this: The maximum amount of memory that can be addressed with a 32-bit machine (which uses all 32 bits for addressing) is 4 GiB.2 If you have more memory space in your RAM, that's nice, but the computer won't ever be able to find the label for the data. In other words, the 32-bit machine can't use more than 4 GiB of data.
Without going too much further into gruesome detail (too late?), what PAE does is introduce some tricks so that bigger memories can be addressed (we can have labels for more bytes of data) and therefore these bigger memories may be used.
Let's now consider the amount of data that could be addressed by a 64-bit machine that used all of the bytes for memory labeling/addressing. The labels could go from
zero (0) -- 64 zeros in binary, hex: 0x0000000000000000 --
to
18 446 744 073 709 551 615 = 18.4 quintillion = 18.4 billion billion -- 64 ones in binary, hex 0xFFFFFFFFFFFFFFFF. We have addresses for 18.4 billion billion bytes of data. That's 18.4 Exabytes = 18 447 Petabytes = almost 18.5 million Terabytes. According to Wolfram|Alpha (screenshot_64), that's equivalent to 1/54 of the information content of all global data. Compare that to the 9/10 of a single-layer DVD that Wolfram|Alpha notes can be stored with 4GiB (screenshot_32).3
The NX Part
In practice, 64-bit machines do not use all 64 bits for addressing memory - they don't need to do so, a fact that I hope was illustrated by the 1/54-of-the-planet's-data discussion. As the PAE wiki article states in its second paragraph,
The page table structure used by x86-64 CPUs [64-bit machines] ... uses the topmost bit of the 64-bit page table entry as a no-execute or "NX" bit, indicating that code cannot be executed from the associated page.
There's more information in the NX-bit Wikipedia article. The basic idea of an NX-bit is that it indicates that the byte of memory addressed by the 64-bit label(_plus_NX-bit_plus_other-stuff) can be marked so that it can't be used by a running program. Among other things, this prevents the type of attack described at the beginning of this answer.
Now, let's return to the fact that the checkbox is for PAE/NX. The same tricks used to make more memory locations accessible can also be used to add in an NX-bit. Again from the second paragraph of the PAE Wikipedia article,
The NX feature is also available in protected mode when these CPUs are running a 32-bit operating system, provided that the operating system enables PAE.
Notes:
1) This answer shows my discovery process. I will be more than happy if anyone needs to clarify or correct anything I've written.
2) In practice, all 32 bits are not generally used for memory addressing, so the size of memory addressable by a 32-bit machine can be less that 4 GiB
3) Another interesting comparison of the amounts of data comes from this source (archived).
According to Videomaker, "One hour of standard definition DV footage requires approximately 12.7GB of storage; approximately 217MB per minute. By comparison, one hour of RAW 4K content requires close to 110GB of storage; approximately 2GB per minute."
So, a 32-bit machine could use enough memory for either 15 minutes of standard definition DV (video) or 2 minutes of raw 4K video. (Note that with video codecs being as they are, I can get almost 12 minutes of 4K video in compressed MP4 format before my older Android phone hits its 4GB file-size limit.)
On the other hand, a 64-bit machine could use enough memory for either 165 643 years of SD DV (video) or 19 131 years of raw 4K video.
I'll put down some other references I found useful while writing this answer.
64-bit / x86_64 or x_64 (archived) VS 32-bit / x86 (archived), think of the Program Files (x86) (archived) folder on Windows or the _x86, x86_64, x64 that you sometimes see in installation filenames.
Using software from previous (not-as-big-of-a-bit-number) architectures (archived)