The pedometer works a lot like those old Pikachu toys did. You clip it to your belt when you go out for a walk, to school, or to the store, or just sit there shaking it. As it detects steps or shakes, it gains "Watts" which are used as a form of currency. At ten watts, you can run into a wild Pokemon and try to catch it. At three, you can use the Itemfinder.
When you're trying to find a wild Pokemon, four blocks of grass show up. You choose one of the four, and you may or may not find a Pokemon. When you catch it, it gets stored on the Pokewalker until you can connect it back to your DS.
When using the Itemfinder, six blocks of grass show up. Again, pick one, and you may or may not find an item. You can store ten items on the Pokewalker until you connect it back to the DS.
You encounter different Pokemon and items depending on what area you are in. Currently there is one area you can get through a special event, and there might be more (though I'll probably miss it anyway because I always get my games late).
As your walking, your Pokemon's happiness and experience (I think) go up slightly.