Let's make it easy:
You can use the round flat batteries found in watches (which you can buy in a store similar to RadioShak)
All you have to do is open the back of your pokewalker and switch the batteries
Now according to the manual (because I READ IT) the battery will live around 4 months if you use your pokewalker max 30mins/day and 10,000 steps/day.
When the battery dies our is about to die, you don't have to worry about loosing your pokemon because the pokewalker is set to save once every hour.