How many of those LEDs do you want to drive, and do you want to drive them independently or all together? Or a mixture?
As Mike says, a switching regulator is the most efficient way of driving them. A less efficient alternative is to use mosfets as constant current sources. If the Maplin 3W LEDs are the ones I can see on their web site, they all run at 700mA and they drop typically 2.3, 3.6 or 3.8V depending on colour. A 9v battery won't handle 700mA well (a lithium one could just about do it but would only last an hour or so), so I suggest a 12v SLA battery (also available from Maplin). Connect 3 LEDs in series to drop between about 9 and 10.5V, then the voltage dropped in the constant current source is no more than 3V. See http://www.pcbheaven.com/userpages/images/LED_driving_and_controlling_methods_14.png for the constant current circuit, but use a chain of 3 LEDs instead of the single one indicated, and connect the top end of Rg to the Arduino output instead of to the supply. Rg should be around 1K and Rs should be 1 ohm. The mosfet will need a small heatsink.
If you want to drive all the LEDs independently, then you could use a 6V SLA battery and one constant current driver per LED, but it will be less efficient.