Searching online I found lots of useful informations, like e.g. wiki says:
The accuracy of step counters varies widely between devices. Typically, step counters are reasonably accurate at a walking pace on a flat surface if the device is placed in its optimal position (usually vertically on the belt clip). Although traditional step counters get affected dramatically when placed at different angles and locations, recent advances have made them more robust to those non-ideal placements. Still, most step counters falsely count steps when a user is driving a car or makes other habitual motions that the device encounters throughout the day. This error accumulates for users with moderate commutes to work. Accuracy also depends on the step-length the user enters. Best pedometers are accurate to within ± 5% error.
On medicinenet one can find an overview on the topic. A useful quote on the topic here is this:
The accuracy of pedometers has been carefully studied because they are frequently used in studies and researchers demand to know if they are reliable and accurate. Research shows that pedometers tend to count steps more accurately at speeds greater than 3 miles per hour (mph) than at slower speeds. Accuracy can exceed 96% when speeds exceed 3 mph, whereas the accuracy drops to between 74% and 91% at speeds from 2 mph to 3 mph, and it drops even further to between 60% and 71% at speeds below 2 mph. The error has to do with the insensitivity of pedometers to detect steps when people shuffle or drag their feet at slow speeds. Detectable vertical movement of the hips is necessary for pedometers to work well.
The two types of pedometers differ in terms of accuracy depending on your speed and your habits:
Piezoelectric pedometers tend to be more sensitive than spring-levered at slower speeds and so they may be preferable for individuals who walk slowly. In addition, the tilt of the pedometer is critical for performance with spring-levered devices, but not so with piezoelectric devices (the piezoelectric mechanism is not position dependent). For example, a pedometer may tilt forward into the horizontal plane if an overweight individual with excess abdominal fat wears one on their waist. Tilt in a spring-levered pedometer can throw off the accuracy by as much as 20% at fast speeds and 60% at slow speeds. A piezoelectric pedometer does not have this tilt error except at the slowest speed (less than 2 mph), and the error is less than 10%.
More infos and tests on specific pedometers are given on walking.com.
I don't know if they compared to GPS data in the tests but I think GPS is always more accurate to measure your distance. These days you can find GPS watches so size/weight is not really a matter (but maybe the pricing).
Before you asked this question I also had no clue about the accuracy but reading a bit on the topic I think I am not going to try one on the trails ;)