After loading my IPSW file (iPhone2,1_3.07A341_Restore) redsn0w prepares the jailbreak data correctly.

I can click on the next few screens (selecting only Cydia) until the instruction screen that tells me to put the iphone into recovery mode where the next is greyed out.

I'm on an iphone 3GS

Version 3.0(7A341)
Modem Firmware is 04.26.08.

Can anybody help me out?

Ok here are the two things you need to check

You are describing the correct firmware/IPSW for 3GS but make sure that is the one you are selecting when you open redsn0w (as the file names for 3G and 3GS ipsw are similar but it determines the course redsn0w will take)

Secondly, for 3GS the redsn0w process is different.
You need to have the your 3GS turned off completely and UNPLUGGED when you start redsn0w, then you HOLD the home button & PLUG IN the iphone NOT releasing the home button UNTIL redsnow takes over.

The above directions are given within the redsn0w, please follow them exactly knowing that steps are different and the latest release of redsn0w (the 0.8 version) does it differently to make things easier.

Good luck!