He is describing a boost converter which steps up voltage at the expense of current. To quote from the Wikipedia page on that subject:
A boost converter (step-up converter) is a DC-to-DC power converter that steps up voltage (while stepping down current) from its input (supply) to its output (load). It is a class of switched-mode power supply (SMPS) containing at least two semiconductors (a diode and a transistor) and at least one energy storage element: a capacitor, inductor, or the two in combination.
As an example, an Arduino Uno consumes around 50 mA from the power jack (at 9V) running a "do nothing" sketch like this:
void setup () {}
void loop () {}
You could say that this is consuming 450 mW of power.
9V * 0.050A = 0.450W
To run from a lower voltage the boost converter (say, 3V) you still need to get 450 mW of power, so therefore it will consume a higher current:
0.450w / 3V = 0.150A
In other words, we now need 150 mA (3 times the current) since we have 1/3 of the voltage.
Also, these converters are not 100% efficient. Say a particular converter is 90% efficient, that means it requires even more current (150mA / 0.9 in this case, being 166 mA).
The efficiency is not linear anyway. It varies somewhat depending on the input voltage and the load. There is a question and answer on Electronics Stack Exchange (Boost Converter Efficiency goes down as Duty Cycle goes up?) which discusses this.
Is my understanding correct (higher voltage = lower current)?
Yes - in the sense that the device consumes power. Thus a higher voltage requires a lower current to deliver the same power. Conversely, if you drop the voltage you need to increase the current to get the same power.
If the current decreased then why was this still an adequate power source for Arduino? Does current not matter?
Yes it matters. You need a certain voltage, with the capability of providing enough current. In this particular case if your batteries can supply 166 mA then the Arduino can still run.
What are the practical limits of this type of conversion?
You will eventually exceed the capacity of your battery to supply enough current. A more elaborate Arduino circuit may involve LEDs and motors. The higher current drain may exceed what the battery can supply, or possibly it will just be drained quickly.
Another factor is that batteries are less efficient when supplying higher current (the quoted mAh figure for a battery is usually for quite a low current). In other words, if you double the current drawn from a battery, the time the battery lasts is not half the time, it is less than half the time. One of the reasons for this is that batteries have an equivalent series resistance (ESR). At higher current drains there is a larger voltage drop over that resistance (some power gets turned into heat, in other words). Thus it isn't practical to try to get 10 amps from an AA battery. The battery will just get very hot.
For instance, he has 4 AA batteries with 1.2V each. He says "that's not going to be enough for Arduino" so he then passes the power through a voltage up-converter and increases it to 9V.
This is actually quite inefficient in the first place. The Arduino nominally can run from 5V (if sent directly to the 5V pin on the board) and 4 * 1.2V is 4.8V which should be close enough for practical purposes.
His idea is to step up the 4.8V using a boost converter to 9V (which in itself has some inefficiency) and then use the voltage regulator on the Arduino to drop the 9V back to 5V which is also inefficient because some power is now being dissipated as heat.
