Procedural textures enable you to define a texture using a predefined formula. This can be something as simple as noise to something as complex as a Renderman shader, which resembles a computer program. These are certainly not as intuitive to use as bitmaps, but they have advantages.
One big advantage to using procedural shaders is that they work at all resolutions. This is important for those who create feature films. In addition, procedural shaders can be manipulated by changing a few software parameters. This allows you to tweak one shader to fit many situations.