I can't speak for the original story, but I have (fresh in today) more detailed destructions for the Story HD.
The battery is glued in with glue stripes on top and bottom (the wide sides) of the battery, and the glue was rather strong in my case. What's more, there is a big hole in the metal frame below the battery where the display is unprotected. So if you try to lever out the battery with a screw driver you can easily crack your display in the process if you didn't know about that hole beforehand. So make sure whatever you do to get the battery out, never try to get any leverage from the middle. Only work at the very sides of the battery. I'd suggest you simply pull hard on the cable of the battery itself, except it may break and you become unable to reuse it for your new battery.
The following picture is from a Story HD Basic with already cracked display I bought from Ebay for spare parts (I finally fixed my bricked Story HD today, yay).
I gave the glue stripes a green tint because they were not easy to see in the image otherwise (sorry for low quality).