The Switching Regulator that momo posted would be perfect for what youre trying to do. I used a similar setup a year and a half ago trying to run a few small test circuits off a deep cycle 12v SLA battery (Basically a car battery... but slightly different...). If you want efficiency, switching regulators are definitely the way to go. You also dont have to worry about it over heating itself either because unlike typical VREGs (Such as the one that the $50 robot uses) which dissipate the excess voltage as heat, this one just cuts the voltage on and off with a cap to filter its own noise.
I found a decent switching regulator for around like 6 or 7 bucks on one of the more common supplier websites last year when I shopped around for one... I want to say I found it on Digi key. If memory serves correctly, It came as an ~9 pin IC that looked like a typical audio amp. I forget its electrical properties though.... ill try to find it again and send you a link