I very highly doubt it's normal. The voltage of the battery I don't think is high enough to produce that kind of effect under normal operation.
The only thing I can think of is if your hand is damp and you're touching both the positive and negative poles of the battery. I don't have my Axim yet (this week hopefully) but I think from pics I've seen that the Axim's battery is completely inside and it with no battery poles showing. If there are though, that's your culprit.
The same principal applies to a standard 9V battery. If you short the poles with a dry finger, nothing happens, but if you do the "tongue-test" you get a good zap, especially if it's a brand new battery
The only times I feel an electric shock of that kind is if I touch the inner wire of a coax TV cable to a vein or when I'm unplugging my car sometimes I get a little fuzzy feeling in my hand. Never felt it on a PDA though.
Good luck!