I've been putting a lot of thought into procedural generation of content for a while and I've never seen much experimentation with procedural music. We have fantastic techniques for generating models, animations, textures, but music is still either completely static or simply layered loops (e.g. Spore).
Because of that, I've been thinking up optimal music generation techniques, and I'm curious as to what other people have in mind. Even if you haven't previously considered it, what do you think will work well? One technique per answer please, and include examples where possible. The technique can use existing data or generate the music entirely from scratch, perhaps on some sort of input (mood, speed, whatever).
Cellular Automata - read.
You can also try it out here.
Edit:
rakkarage has supplied another resource: http://www.ibm.com/developerworks/java/library/j-camusic/