A good place to start might be some reading material...

We're planning a project that has similar requirements... we want to store a massive game universe with minimal data, so I'm planning on seeding. One numerical seed gets pumped into various algorithms to generate each world.

I found a series of books, which have so far proved very interesting, although I can't comment on implementation because I haven't got that far yet.

The books are:-

Infinite Game Universe: Mathematical Techniques - This covers the maths behind generating predictable random numbers, fractals and a bunch of other stuff relating to seeding and that kind of technique (or at least thats my interpretation of the content so far)

and

Infinite Game Universe: Level Design, Terrain, and Sound - I've not gotten too far into this one yet, but what I have skimmed of it seems like it could be useful reading based on your opening posts.

Both are by Guy W. Lecky-Thompson, published by Charles River Media.