Reddit mentions of Algorithmic Composition: Paradigms of Automated Music Generation

As others have pointed out already, there are a lot of different ways to generate procedural content. Some algorithms work well at certain tasks, while others don't work well for those tasks.

In my experience, it's really difficult to come up with one algorithm that is so versatile that it can do everything. Usually, a layered approach is what ends up working, with multiple algorithms stacked on top of each other.

I strongly encourage you to get started on working some of this stuff out. Procedural content generation can be much more difficult than it looks, especially if you want to generate material on the fly (as opposed to generating something then editing it before using fixed materials in the game). It usually takes a lot of experimentation and a lot of trial and error to figure out what works and what doesn't. What sounds good in your head is usually far from perfect in practice.

I'd also strongly encourage you to do some reading on the subject. I mostly deal with algorithmic music, so I can suggest books on that. Algorithmic Composition covers AI algorithms that can be used for procedural content generation in almost any area. Maybe someone else can suggest a book that deals with game content?

Another good thing to study is noise algorithms. Perlin Noise is a type of noise that is incredibly versatile and adaptable. Also, the algorithm for generating Perlin Noise is relatively simple and available in most game environments. I strongly encourage you to explore that.

You will find that naive noise algorithms, such as pure randomness, are largely ineffective, but with slight modifications, and a little bit of study, you can find other noise (= data) algorithms that are still simple, but possibly useful, such as Brownian Motion.

Anyway, some things to think about.

Maybe start here for an extensive overview of literature and software: algorithmic.net

A pretty good book on algorithmic composition: Algorithmic Composition: Paradigms of Automated Music Generation

There's also a book available for athenaCL, a "modular, polyphonic, poly-paradigm algorithmic music composition system in a cross-platform interactive command-line environment" written by its creator Christopher Ariza, but I've not read it yet. It looks to be quite in-depth and much needed considering the complex nature of the athenaCL system.

There are lots of people who have approached automatic composition before. (don't know if that's encouraging or discouraging)

This book gives a good overview of the different approaches, which might give you a better idea of where to leap off:
http://www.amazon.com/Algorithmic-Composition-Paradigms-Automated-Generation/dp/3211999159/ref=sr_1_2?ie=UTF8&qid=1341245959&sr=8-2&keywords=automated+composition

For your goals, you might want to read the sections on grammars, markov models, or neural networks, which tend to focus on the high level structural aspects. A lot of the other stuff is unrelated.

About rendering as sheet music, I found this interesting library:
http://www.vexflow.com/