I don't think one would work cause just like in another thread about a compass, the BB doesn't have what an iPhone has. None of the tilting functions or the shaking or whatnot. I just don't think they're built for stuff like that.
BB's don't have, whats the word, acceleromoters? in them. The only way a pedometer could work is by using the GPS somehow which may not be very accurate.
When GPS was mentione, it reminded me, there is a program called bbTracker: bbTracker - Trac I don't know if it will work for what you want, but it might be worth checking out.