You need 5 V for the circuit. A regulator will reduce the battery voltage down to 5 V and it doesn't matter what the battery voltage is.
However, there are limits. The lower limit is the above 5 V, and the amount that it is above 5 V is called the "drop out" voltage. A standard regulator has a drop out of about 2 V so you would need at least 7 V on the battery to maintain 5 V.
That doesn't seem so bad with a 9 V battery, but in fact 9V batteries will soon drop below 9 V when used, and a lot more current can be got out after that, but the voltage will continue to fall. After about 6 V there isn't much left.
If you use a low drop regulator, you will still get 5 V out when the battery is down to 5.5 V so you will get more out of the battery.