How would I procedarally generate a terrain?

I don't even know where to start looking. I heard something about using Perlin noise, but how?

Perlin Noise is http://www.unifycommunity.com/wiki/index.php?title=Perlin_Noise

Although you can find road and terrain generators for unity, I couldn't find a free one yet. Except for http://www.unifycommunity.com/wiki/index.php?title=MazeGenerator that is not fully finished yet.

I would try using TerrainToolkit, available from the Resource -> Extensions part of the main unity site. Then you could use the API to create the terrain at runtime.