If by "best" you mean "most efficient", then you want a switched-mode power supply, or more specifically, a buck converter. Efficiencies above 70% are common, and above 90% is possible with careful design and selection.
With such a device, you may indeed be able to use a 12V battery without any more loss than you would have with a 6V battery.
The LM317 is a pass transistor driven by an error amplifier, essentially an op-amp plus a transistor. An op-amp plus a MOSFET is not very different, and you will not improve on the efficiency of an LM317 with any combination of op-amps and MOSFETS that don't involve rapid switching, and probably an inductor. Without switching, you have a linear regulator, and the only place excess voltage can go is into heat.
Electrical power is the product of current and voltage:
$$ P = IE $$
and as long as you have any device with a voltage across it and current flowing through it, you are converting electrical energy into something else, usually heat. Non-linear regulators avoid this problem by rapidly switching between periods of high voltage and low current, and low voltage and high current, except in an energy storage device (an inductor) which can store the electrical energy in something more easily recovered than heat (a magnetic field).
The choice between using a simple 3 terminal linear supply and a switch mode power supply depends on the current you need, as well as the difference between the input voltages you have and the output voltages you need.
You did not specify the current draw requirements for the LED strip and the Arduino. You specify that you expect to use a buck converter for the LED strip, why is this? If the input voltage is only slightly higher than the regulated voltage, a high current low-dropout linear regulator will be almost as efficient, for much less complexity. Recall that the formula for efficiency in a linear regulator is Efficiency ~= Vout/Vin; if Vout is very close to Vin, then the efficiency will be close to 100%. A low-dropout linear regulator such as the LT1185 regulating from 15V to 12V will be approximately 80% efficient, which is better than many switch-mode regulators.
Your real question is how to power the Arduino, which runs at 5V. In this case, it is true that the efficiency of regulating from 12V down to 5V via a linear regulator will be poor, approximately 40%. However, your total power loss is proportional to current: P_loss = I_load*(Vin-Vload). The Arduino's exact current draw depends on which peripherals are enabled and what the code is doing, but assuming you are not doing much more than using the serial port to display some patterns, a current draw of 50mA is reasonable. Therefore, your loss in using a common linear regulator (such as a 7805) is only 350mW, which is reasonable if your application is not battery powered.
Best Answer
The most efficient way to create a lower voltage at higher current from a higher voltage at lower current is a type of switching power supply called a buck converter. For a buck converter, (watts out) = (watts in) - losses. For a linear regulator (current out) = (current in) - losses.
Buck converters up to 85% or so efficient are relatively easy to make yourself. You have to wake up and take it seriously to get over 90%. Getting 95% requires someone that knows what they are doing really applying themselves to the problem.
There is much written about buck converters out there, and the term "buck converter" should be a useful search term. Therefore I'll only explain the general concept briefly.
When the switch is closed, current builds up in the inductor. When the switch is opened, the instantaneous inductor current must continue to flow. D1 provides a path for this current. Since the voltage accross the inductor is now negative, the current in it decreases. The switch opens and closes rapidly to add current to the inductor when closed and causes the inductor current to ramp down when open. The fraction of the time the switch is closed regulates the overall output current. This fraction is usually modulated by a feedback loop to regulate the output voltage.
Due to the current path thru D1, the output current is higher than the input current. If all the components are ideal, no power can be dissipated, and all input power is transferred to the output.