Kat- When you say that you're beginning LSOH rehearsals, might we presume that you're puppeteering Audrey II? If so, then you definitely will be getting a workout! The first time I did the show, I did a lot of aerobic exercise to develop stamina, and just a basic regimen of weight work with dumbells to develop upper body strength.
But whatever you do, I would suggest getting into the puppets as soon as possible. Its only then that you discover which muscle groups get the most strenuous use. And also you need to get used to the stifling heat, and to sitting absolutely still from "Somewhere That's Green" through "Mushnik & Son". Immediately after that was (for me, anyway) the biggest workout in the entire show, "Feed Me/Git It". Its the fastest lip-syncing in the show, and there's some pretty wild movement ie. upper body and arms animating the pod/trunk, and legs animating the roots.
Playing Twoey is an incredible experience. The first time I did it, I lost 15 pounds. Sadly the second time, I didn't lose any weight, and the third time I might actually have gained a bit!