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

Although you can find road and terrain generators for unity, I couldn't find a free one yet. Except for 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.