Sometime before history began, a human (or a reasonable facsimile) stacked some rocks up and said, "Voilà!, a stone wall." Although the techniques have been refined since then, they are still variations on this theme. A person who builds with stone is referred to as a stonemason.
Stone walls come in two basic types:
Dry stacked stone walls do not contain any mortar and must be put together in such a way that gravity holds the stones in place. Often soil or smaller stones, or a combination of both, are used to help lock the larger stones into place. Dry stacked walls are often used as retaining walls where a steep slope would otherwise cause erosion problems. For someone who wants to try this, careful consideration needs to be given to the amount of force that soil will apply to the uphill side of such a wall. A dry stacked wall used as a retaining wall should be widest at the bottom (one half of the height) and sloped towards the buried side (two inches of slope for every foot of height). Often, long stones are incorporated that are buried into the slope at right angles to the face of the wall. These are referred to as "dead men". These help gravity to do its job of keeping the stones in place.
Mortared stone walls are similar to block or brick walls in that mortar, which is a mixture of portland cement, lime and sand, bonds the stones (or bricks or blocks) together. Such walls may range from a stone veneer, which is attached to a wall built from other materials, to massive free-standing walls. The Great Wall of China is actually constructed of both dry stacked and mortared stone as well as other materials such as bricks and soil.
It seems that there are about as many styles and methods for building walls with stone as there are individuals undertaking their construction. There are a few "rules", though, that should be followed if the stonemason wishes his or her creation to outlast the builder.
Rule #1 Keep vertical joints as short as possible. The joints in stonemasonry are the spaces between stones that are filled with mortar. In dry stacked walls, the joints are the interfaces between adjacent stones. In either case, a vertical joint should be broken by placing the stones so that each stone above the first course, or row of stones, is resting on top of two or more stones below it. Long vertical joints make weak walls!
Rule #2 A stone wall is only as good as its foundation. At the very least a trench should be dug that is deeper than the soil freezes during the coldest weather expected. A reinforced concrete foundation may be poured in the trench, or the stonework may be started in the bottom of the trench. This is done to minimize frost heave.
Rule #3 This one applies only to mortared stone walls. Stones should not touch one another at any point in the wall. The mortar joint should be continuous and tightly packed, with no air gaps.
There are many resources one can turn to for further information on stone walls and their construction. A random sampling follows.