Procedural is just a very generic name for a myriad of techniques to generate stuff (like saying “rasterized” when you mean “painted it in photoshop”). It means that unless you try and compress something, you’re generating something dynamically. But it can’t be used for everything, quite the contrary.
On .kkrieger case, for example, textures are generated by code - instead of graphical files, they have some functions that generate the images. For example, a guy draws a square (by code), applies noise, some emboss, change color, voila - it’s metal, done on whatever size you want, with like 100 bytes (sans graphical api). Then he duplicates it and changes the color and that’s a “brick”. The same can be done for wood, some kinds of grass, water, walls, etc.
But of course that’s really limited, If you look at kkrieger’s generated textures you’ll notice they’re fairly ‘simple’. So it’s a programmer playing the part of what a designer would do on, say, photoshop. It’s not practical for real games because you have to code the entire steps taken to draw that thing. For textures that are hand-painted, there’s no mathematical equivalent.
On megatextures’ case, apparently it’s procedurally generated on the tool (so you can lay some kind of textures fast, like drawing grass until a certain height, snow and water to other height, stuff like that). It’s done like that to save design time, but the end result is just a flatten image because if you want to add some touches to it, you can.