There are also 8 and 10V regulators commonly stocked if the 9V isn't findable.
You will need some heatsinking on an external regulator, a clip-on one ought to be enough but
you can calculate the heat dissipation and work it all out if you measure the current consumption
of your Arduino and its LCD etc.
The power dissipated in a regulator is the difference in input and output voltages (in volts) multiplied
by the current (in amps) - gives power in watts directly.
Heatsinks have a C/W specification which is the temperature rise per watt dissipated (in free air), and
so you can choose a heatsink that will keep the regulator cool enough.