There are a couple of designs for accelerometers. The one that texaslabrat describes doesn't really have (easily visible) moving structures or elements per se. Basically, the way that design works is that you get a crystal structure that has piezoresistive properties. That is, the crystal changes resistance depending on the amount of mechanical force exerted upon it (think about the sensations your body feels when the car accelerates and imagine that your body could change resistance accordingly ). There are also crystals that have piezoelectric properties which, as you can probably guess, generate a voltage when a mechanical force is induced upon it. There's even a method for building accelerometers by determining changes in capacitance in objects.

And to answer your second question, yes, you can build a a pedometer app that uses the accelerometer. Nokia made one for Symbian S60 3rd devices (I used it on my Nokia N95 and it works pretty nicely). I'm not sure but I'd expect the stand-alone pedometers to use both analog as well as accelerometers to detect steps.