Both kernels split the virtual address space into a user portion and a kernel portion. The kernel portion is shared between all processes in the system, and so the kernel is limited to that much directly addressable memory. Each user process in the system has its own user portion of the address space. Classically this split was done in the middle, giving each half 2gb. Windows can be directed to move the split to 3gb for user and 1gb for kernel with the /3gb boot.ini switch. The linux kernel is rather configurable at build time, and last I checked, the Ubuntu kernels build with the 3:1 split.
PAE allows for 64 gb of physical ram to be addressed, but any given page table still is limited to 4gb. Because there is only one kernel portion of that address space shared between all processes on the system, it is limited to 1 or 2 GB of directly addressable ram no matter what. Additional physical memory can be used, but it has to be only partially mapped into the virtual address space at any given time, and the mappings changed when needed. Because each process has a separate user address space, you can have, for example, 5 different processes that each have 2gb of their own memory that maps to different parts of 16gb of physical ram you have installed, and the kernel using another 2gb.
Note that the filesystem cache does not have to keep pages mapped all the time, so it can use plenty more of that physical ram, and the kernel automatically maps bits of it when needed, then unmaps it so it can map other pages. This trickery allows the kernel to use many gb of memory for the cache, and a few hundred mb for other uses, even when the kernel only has 1gb of virtual address space to play with.
Also worth noting is that in recent versions of Windows, Microsoft has instituted various artificial product licensing limitations. The Windows 7 Pro I am stuck with on my PC at work refuses to use physical ram addresses > 4gb even if I enable PAE, which results in it only being able to use 3.4 of the 4.0 gb of ram installed, since a chunk of the ram is relocated over the 4gb mark to leave room for things like the video ram to be located under 4gb.