The Question of Stone
For a dry-stone wall, your local stone should be of a hard, flat-cleaving stone such as shale, slate or schist. You want long angles -- meaning flat tops and bottoms -- when possible, so look for stone that naturally breaks into those shapes to ensure strength and durability of your finished project. The worst choice is igneous rock, whether found in the ground or in water, as its formation creates shapes that will work against you in wall building. (If you love the look of igneous rocks, of course, the mortared-wall choice is still available, as you'll see.)
Since sedimentary rocks are pressed by time and gravity into the same useful configuration as the hard stones mentioned above, they're a good choice as well. In fact, the relatively softer nature of metamorphic and sedimentary rocks can be a good thing, since you'll probably have to do a little stonemasonry to make everything fit together. Remember that "soft" is a relative term: Walls and structures made of sandstone and limestone -- both sedimentary rock -- can still last thousands of years!
It's just a matter, again, of considering your local conditions: A lot of wind from a dusty plain can shave limestone down over time, while a more volatile climate full of freezes and thaws actually works better with softer stone, since it's less likely to crack and change shape. Of course, a major part of building the wall is taking those forces and changes into account, and being mindful of those factors starts at the outset.