What battery size/type should I use (and wiring tips for LEDs?)
The LED's I'm looking at have a Forward Voltage of 3.0-3.6v


That would be white, green, and or blue LEDs for that Vf range.
They are probably low efficiency LEDs.  Not good for a battery powered project.
The Vf is too high for a high efficacy LED.  Efficient LEDs will have a 2.7-3.0 Vf.  

I'd use either a Lithium or Li-ion battery.
Using a good efficient LED, such as the Cree C503B series LEDs, you could use a single Lithium CR-2032 coin cell (3 grams). A better (but heavier, 45 grams, and larger) option would be a $4 18650 Li-ion and would last many (100s) hours per charge or you can run these Cree LEDs super bright. 

The Cree LEDs will cost under 25¢ each and will pay for themselves in batteries compared to cheaper LEDs. 

I would be leaning toward the 45 gram 18650 Li-ion.  I'd use a milling machine with an 18 mm ball cutter to embed the battery in the bottom of the body. If using the CR2032 coin cell(s) I'd use a 20 mm end cutter.  

See also this answer:  Will this schematic work - basic LEDs + strips