PAE (sometimes called PAE-X86) was first implemented by Intel in 1995 in certain models of the Pentium Pro. The PAE IA-32 architecture supports 4 additional address lines for memory selection, so physical address size increases from 32 bits to 36 bits. This enables 4Gb x 2*4 = 64Gb of physical memory to be accessed. The CPUID flag for PAE support is, naturally, PAE. Since then virtually every 32-bit CPU produced comes with PAE support.
Even with a PAE-enabled CPU, the IPL32 programming model (IA32 flat memory mode) continues to be able to only see 4 Gb of memory. You need a PAE-aware Linux kernel which uses an 3-level page table hierarchy to access more than 4Gb of memory. Depending on how they were written, applications that wish to access more than 4Gb of memory may need to be modified.
The Linux kernel first supported PAE as a build option in version 2.3.23. Initially seperate 32-bit and 32-bit PAE kernels were the norm for Linux distributions. Nowadays, however, major Linux distributions, except for Debian, only provide a 32-bit PAE-enabled kernel.
For a detailed explanation of how PAE page table work, I recommend this Wikipedia article and this Microsoft article.
Note that 64-bit kernels do not need or use PAE.
