Just adding a cap seems easier to me, (rechargeable battery will need recharge circuit, and pass-through diode [kind of like a voltage source-selector] at the very least, no?) but the question remains whether that will be enough to hold you over.
You've gotta do the math though to see how much juice you need. Current will have to be measured from the leds + any leakage / quiescent through the step-down system. Voltage max might be 9 V but more than likely is 9VRMS if you're turning the crank steadily. Voltage min is min input to the step-down circuit.
Here's a good time to make you aware that capacitors store a lot of energy. If you short them, especially large ones, you're in for a bit of a surprise. I think anything over 500uF starts to garner my attention, and you're going to need a lot more than that. You'll need to consider a discharge circuit to make sure you don't hurt yourself or blow stuff up with the super cap (no joke), but I believe if the light circuit is constantly connected / on you should be ok (anyone else care to pitch in on that?).
edit1: and on second thought (for the very same reasons described above) just do the battery. If you don't know what you're doing things can get problematic quickly. Search for battery power source. There's plenty of info around on this sight. Main points. Separate with diodes. Make sure your step-down output is HIGHER than the battery output (but that your led's can still run off battery output). If the step-down is putting out 3.3 (probably?) then use 2 nimh (2.4v). Done.
Battery in parallel with main power source
edit2: Okay so maybe a 9V cap isn't going to kill you..., but it's going to to put on a show if it shorts.
Guidelines for determining shock hazard of capacitors