pedometers just use accelerometers. an accelerometer is a device that measures acceleration in one or more directions. by tracking the forward/back acceleration of a person's leg, you can quite easily find out how many steps they took. shouldn't be hard to build from scratch, depending on what accelerometer you choose. analog devices makes some with PWM or analog outputs I believe (ADXL202 comes to mind) that makes them easy to interface with a microcontroller.
if you visit sparkfun.com they have all sorts of products dealing with the ADXL accelerometers, from the chips themselves, to breakout boards, to serial interface boards, and even assembled, ready-to-use serial accelerometers.