Step 1: Parts needed
1x Arduino Microcontroller (to act as the programmer, you could use an ISP to program them though.)
1x ATTiny45 / ATTiny85 microcontroller
1x 74HC595 Shift Register
1x HD44780 compatible LCD
1x LED (for testing the microcontroller)
1x Resistor for the LED (use one that is right for the specs of your LED)
1x Potentiometer for LCD contrast (You can connect the contrast to ground
Loads of wires!
Step 2: Connecting the ATTiny to Arduino
Start by connecting ATTiny pin 4 to Ground.
Connect ATTiny pin 8 to +5V.
Next, connect the following cables from the ATTiny to Arduino:
ATTiny pin 1 to Arduino pin 10,
ATTiny pin 5 to Arduino pin 11,
ATTiny pin 6 to Arduino pin 12,
ATTiny pin 7 to Arduino pin 13.
In some cases such as using the new Uno boards, ou will need to connect a 10 microfared capacitor from the Arduino reset pin to Ground. Make sure the capacitor ground (-) is connected to round as it is polarised. In my case everything works just fine without one, but there may be some issues that I'm not aware of. If anyone is aware of any then please post them in the comments.
You are now good to go, next is the programming!
(reference: High-Low Tech)