Is there nothing connected to the Arduino that also needs power?
If you want to figure out what kind of battery you need, you must know two things:1) How much power everything is drawing. You don't know that. Or at least you haven't mentioned it here.2) How long you want this to operate between battery charging or replacing.Also helpful to know:3) What kind of constraints on size (volume, weight) you have for this project.4) Whether you want to use rechargeable or replaceable (non-chargeable) primary cells.
These battery cables ( http://cgi.ebay.com/2x-9-Volt-battery-adapter-Arduino-/270616862179?pt=LH_Defaul...) can be a little more secure then just stabbing wires into the Vin and ground pins. Keep in mind if you try to power more then around 4-5 leds your voltage will start to sag as the current capacity is pretty poor with those batteries plus they really are expensive (around $2.50) for the little mah ratings they supply.
Is it possible to find these at any electronic star