Yea that was what I figured. Really it's the same scale of project as the Metaworlds, or NEI, or 3d chunks. Still people HAVE managed to do all of those.
Metaworlds I have an idea of how it works, and it's just storing block data as part of a Entity. The hard part was probably the rendering and making redstone work (based on the TinyBlocks mod: getting redstone and pistons to work was difficult, but eventually done). Requires a fair bit of memory and CPU overhead, but the data required is all freely accessible. Various blocks in various mods offer ways to store "blueprints" of structures and then rebuild them else where. Same principle, except that the data is only stored, not also rendered and modifiable.
NEI just has to look at the Recipe Registry, which already has a standardized format. Any mod can actually go in and request recipes with a specific output and even remove them or do other things.
3D chunks / cubic chunks is a bit more complex, but it involves restructuring some vanilla base code, I believe. I'm only vaguely aware of how chunks operate down below the Chunk class, but I do know that Mojang made a mistake when assigning block x/y/z coordinates to the byte array, as Mystcraft actually went in and swapped them with its own Chunk Provider for its worldgen. X and Z range from 0 to 15, or 4 bits. Mojang stored them thusly (IIRC):
x<<12 | y<<4 | z
Allowing Y 8 bits. Rather than
y<<8 | x<<4 | z
Which would give Y an unlimited* value, rather than X (which doesn't need it).
*Or at least, the larger selection of a 32 bit integer than the limited 8 bits granted by Mojang's code (which is why vanilla has a world height of 128). Now that I've typed this, I think that's specifically worldgen and that the chunk data class stores Y as a separate bytearray, but the worldgen code was never updated to account for it, which is why mountains range up to 128 but you can build to 255 (max value of a byte).
Heck, vanilla worldgen classes still don't support block values above 255!
Forge has had to supply additional support for modblock worldgen.