Hi BaMzE. The battery depends on the driver, which appears from the description to take a "5.5V~15V" input though they do not explicitly state it. There is not much info on that driver though I did see some discussion of a
similar board here and
here. I think you could probably put together a pack with AA NiMh cells and holders (like NeilT's pack above), and if it behaves like the other KD board, the current draw will go down with a higher voltage pack - otherwise I am not sure how well the cells will hold up to a high current draw. If you do not have a multimeter it would be a good investment for this hobby, especially with a driver such as this with some unknowns. I'm sure somebody else can comment on a battery suggestion for your driver. I would not use L-ion unless you can get a commercial pack that is capable (current and capacity wise) or really know what you are doing since there are real dangers with L-ion cells (and please never solder to batteries since they could be shorted with just a small blob of runaway solder - trust me on this

).
A lot of the parts such as cheap no name optics and drivers will be trial and error unless somebody else has already reviewed them. If you buy name brand stuff (Ledil, Polymer Optics, Calrco) you will usually pay a good deal more, but can often get a datasheet beforehand so you know what to order - or see beamshots in this forum or on candlepowerforums.com from other users. If you want to go the safe route with name brand components I suggest checking cutter (even if you don't buy from them they are a good resource - though they are also the only place to get many things).
A good place to start looking for cheap parts is at the DX flashlights DIY section
here. Unlike KD, there are plenty of reviews of the parts at DX so you can get an idea of what may work - often DX (and KD for that matter) do not provide info on what optics work with what type of LED's (SSC, Cree, Luxeon) - so it is up to their customers to figure it out (this is where the reviews and discussion forums help).
If you are looking for a different driver, I would go with something that will drive the emitters in series since it seems simpler to find batteries (it seems easier to find cheap high voltage packs with decent capacity than it is to find lower voltage high capacity packs - I may be misinformed on this however).
I have been sticking with wired 1000ma buckpucks (3023-D-E-1000) with an external pot since they seem simple and reliable - and they are potted in a plastic resin so I can be less careful in how I place them in the case (they won't short). The downside is that they are not the cheapest (about $15 - ledsupply.com, luxeonstar.com and mouser.com sell 'em) - I could get several DX drivers for the same price, it is just a bunch of tradeoffs. Everyone seems to have their favorite driver, it is just a matter of finding something that works and is the right price.
Once you have the drivers, emitters and battery picked out, the rest is where you can get creative and either make it really expensive (my forte, though I am trying to reform my ways) or cleverly inexpensive. Good luck!