The white paper in your link explains this very nicely.
The "jiggery-pokery" that Engadget speaks of is not faking the high resolution, but rather going the other way around: the sensor really does appear to have that many tiny little photosites, but under normal use, it pixel bins. (Presumably, the image quality is pretty atrocious at the pixel-peeping level.)
Nokia says:
Pixel oversampling combines many pixels to create a single (super) pixel. When this happens, you keep
virtually all the detail, but filter away visual noise from the image.
The sensor they're using is relatively big (for a compact camera) — they're saying it's a 1/1.2" format sensor, which would be a 13mm diagonal, which is only slightly smaller than the Nikon CX.
Digital Photography Review now has a blog post explaining this, with pretty pictures. One key thing that they note (and which I didn't bother to work out but should have) is that the larger sensor means that the photosites-per-area is the same as for a typical 8mpix cell phone or ultra-compact camera.
And, I'm going to re-quote something they take from Nokia's blog (the link you posted):
5Mpix-6Mpix is more than enough for viewing images on PC, TV, online or smartphones. After all, how often do we print images bigger than even A4? [It] isn’t about shooting pictures the size of billboards! Instead, it’s about creating amazing pictures at normal, manageable sizes.
I sure hope DSLR makers take that same philosophy as large-sensor cameras increase in megapixels as well. (Canon's on the right path with sRAW.)