You can make trees from horses and mazes ;-)


Images for these can be found in documentation for SkeletonTransform and MorphologicalGraph.
Actually, trees are everywhere. Arbitrary expressions have the structure of arbitrary trees. Imagine taking an integral:
Integrate[Sin[(1 - x)/(1 + x)], x]
![integral of Sin[(1 - x)/(1 + x)]](https://i.stack.imgur.com/GRftE.png)
This will give you a pretty random tree if you apply algorithm from this answer - I am giving only the final line with styles here:
Graph[edges, VertexLabels -> First@labels,
ImagePadding -> {{1, 35}, {0, 10}}, GraphLayout -> "RadialDrawing",
GraphStyle -> "ThickEdge", DirectedEdges -> False]

Now on a more serious note: There are probably quite a few different ways to do this. In addition to @rm -rf's answer, I mention 6 other possibilities.
Random Tree Aggregation
Connecting Towns Using Kruskal's Algorithm - Neat, random points in plane construction
Tree Form of Recursive Function Evaluation Steps - can give a key to another approach
Image processing - see above
Random expressions - see above
Randomly cut a perfect tree.
You can generate a complete tree of specified number of levels and branches. Here is a tree of 7 levels and 3 branches:
g = CompleteKaryTree[7, 3, GraphStyle -> "LargeNetwork",
GraphLayout -> "RadialDrawing", VertexShapeFunction -> ({PointSize[0], Point[#]} &)]

Then drop a controlled number of edges, and select the largest connected component. Here are a few random samples like that:
rg = Subgraph[g, Sort[ConnectedComponents[
Graph[RandomSample[#, Round[Length[#] .6]] &@EdgeList[g]]],
Length@#1 > Length@#2 &][[1]], GraphStyle -> "LargeNetwork",
GraphLayout -> "RadialDrawing"] & /@ Range[12]

Note that I use "RadialDrawing"
layout everywhere, which is good for large trees. Of course you can use the standard one:
AdjacencyGraph[#, GraphStyle -> "LargeNetwork", AspectRatio -> .5] & /@
(AdjacencyMatrix /@ rg)

Still, the radial one is excellent for large trees:
g = CompleteKaryTree[10, 4, GraphStyle -> "LargeNetwork",
GraphLayout -> "RadialDrawing", VertexShapeFunction -> ({PointSize[0], Point[#]} &)];
Subgraph[g, Sort[ConnectedComponents[
Graph[RandomSample[#, Round[Length[#] .45]] &@EdgeList[g]]],
Length@#1 > Length@#2 &][[1]], GraphStyle -> "LargeNetwork",
GraphLayout -> "RadialDrawing",
VertexShapeFunction -> ({PointSize[0], Point[#]} &)]

LayeredGraphPlot
$\endgroup$ – rm -rf♦ Oct 17 '12 at 21:10