I've successfully connected a LCD display (**broken link removed**) to my laptop using this circuit: **broken link removed**
The LCD should be powered with 5v and I'm currently using three 1.5v batteries. Now that I'm going to put the circuit in a box, I would like to power it using a 9v battery and I'm not sure how to do that. Will this circuit, http://www.hut.fi/Misc/Electronics/circuits/psu_5v.html work with a 9v battery?
The page says
Power supply voltage: Unreglated DC 8-18V power supply
Power supply current: Needed output current + 5 mA
All you need is a simple 5V regulator, have a look at the hardware pages for my PIC tutorials, the processor boards include just such a regulator to feed the 5V PIC (and LCD) from a 9V battery.
I suspected that I should use a voltage regulator but I wasn't sure how to connect it.
If I understand the circuit on your hardware page, **broken link removed**, correctly, you have connected the voltage regulator in a way similar to the page that I mentioned, http://www.hut.fi/Misc/Electronics/circuits/psu_5v.html. The difference is in the values of the capacitors.
Should I connect the voltage regulator like in the picture that I've attached below?
Yes, that's fine - you don't need to use C3, that was just a capacitor added close to the PIC (which is always good practice).
The values are very uncritical, I used 1uF because they are small, and I had them handy. You must use capacitors near the chip to prevent it oscillating.
Most of my tutorials would be quite happy with a 78L05, in fact my 16F877 board uses one - the others used a 7805 'just in case', and because I happened to have them to hand