1. Start Blender and remove the default cube (select it and press key: x)
2. Add a grid to the scene: Add->Mesh->Grid.
   

   Create grid

   32×32 segments works good for smaller grids

   

   Set segments

3. Select the Shading panel (F5) and go into Material edit mode (the round sphere icon)
4. Click on “Add New”under the Link to Object
   

   Link To Object

   This opens up a new pane

5. Switch to the Edit Texture mode (F6)
6. In the Texture pane click the “Add New” button
   

   Add New Texture

7. Select Clouds as the texture type
   

   Select "Clouds"

8. Now you can adjust the Clouds settings if you want. I will stay with defaults here
   

   Cloud settings

9. Now switch back to Material Edit mode (the red sphere icon)
10. Close to the Texture pane there is now a Map to pane – open it
    

    Map To options

11. All buttons in the Map to pane should be off
12. Now switch to the Edit pane (F9) and enter Edit mode (TAB). All vertices in your grid should now be selected
13. In the Mesh Tools pane click the Noise button
    

    Mesh Tools

    (if you want more height just keep clicking the Noise button)

14. Now you are done
    

    Random terrain result

Tested in Blender 2.49