remember to rough up the surface where you want the solder to be. use either some 320grit sandpaper, a sanding drum on a dremel or small jewelery flathead screw driver and scratch some crosshatch.

in terms of the soldering iron, use one with a big chisel head and about 70 to 80w should do it.

good luck

PS. make sure you melt some solder on the soldering tip first, that will help heat up the surface of the cell faster as the soft solder will take up the uneven space between the tip and the cell. if it's done correctly it should take no longer than 2 to 3 sec to heat up the cell to take in the solder and should flow nicely.