Also, in addition to what Admin said, get some flux, even if the solder you are using is flux-core or rosin-core. Make sure the things you are soldering are really clean, and pre-tin the wire you are soldering to the battery ends. You do this by coating the wire in flux, and then heating it up and applying solder to it, until it is coated with solder. It will work better (and is much easier to do) if the solder is already on the wire, so you don't need three hands. Hold the battery in a vise, so it can't move around while you're soldering it.
As well, after you clean the battery terminals and before you put flux on them, take a piece of fine sandpaper and score the surface a bit - the solder will stick better, but only if the surface is really clean. After you sand, clean it again (preferably with alchohol), and then apply some flux.
Make sure the iron tip is heating both the wire and the battery, and make sure the solder flows properly onto the battery surface - you don't want a glob of solder that is only lightly stuck to the battery. You can usually tell by looking at the edge, where the solder meets the surface - if it overhangs the surface, it probably isn't a good joint. If it flows down to a form a ramp from the surface, you've got a good joint.