Which Voltage Regulator to use?
The battery you have chosen is a typical Lithium Poly with a maximum voltage of 4.2v, dropping to 3.7v according to the description linked to in the OP; however the datasheet says it can be discharged to 2.75v, which is more typical of these batteries..

The RFduino can operate with voltages from 1.9v to 3.6v, with a typical voltage of 3.0v.  (It's too bad it can't operate up to 4.2v like a lot of cell modems do, then it could be connected directly to the battery.)

However if you put a silicon diode with a typical forward voltage drop (Vf) of around 0.7v in series with the battery, this will drop the battery voltage range to 3.5v down to 2.0v, which is just right for the RFduino.  And diodes are much much cheaper than regulators.

The venerable 1N4148 has a forward drop Vf of 0.6v at 1 ma, and 0.8v at 20 ma.