What Battery Voltage to use?

Im currently designing a small robot that uses 2 of these 12v motors, which are manage by the L298N motor controller board, and is being controlled overall by an arduino. Now I have come across an article(Scroll to bottom after clicking link for the schematic of what I am looking at) talking about powering the robot. It talks about using a switching regulator to stabilize the voltage going to the motors, but also has a disclaimer saying switching regulators uses about 1-2v. Now I am currently looking at this 12v li-ion battery.

So one of my question are, will I need to bump up to a 15v battery because of the voltage drop across the switching regulator?

I also want the battery to last as long as possible so efficiency is important. And when it comes to efficiency, then it seems like it would waste a lot of power to use a voltage regulator to drop the voltage to 9 volts for the arduino (which already has a regulator built in, but only up to 12v). I know with this at least I can add 9v battery for the arduino alone.

So overall, how do I maximize efficiency while ensuring the motors and arduino get the voltage they need

A few things going on here. First of all -- voltage != efficiency (at least not necessarily). Efficiency is really a measure of total power output which is $$I \cdot V$$ (where I is current). Next, your 12V battery isn't 12V, it's got an operating range (from your link) of 12.6 to 8.4V, and I assume a typical voltage somewhere in the 11s. That means that based on charge level, it'll range from 12.6 (completely full) to 8.4 (completely empty) and for the most part be somewhere around 11.1 (12.6 / 4.2 is 3, which leads me to believe that it's a 3S battery which will have a nominal voltage of 3.7*3 or 11.1). All of that means that if you need exactly 12V, you won't have it most of the time.