To jailbreak an iPhone 3GS is extremely simple. Download and run a software written by George Hotz. Whom you will recall to be the original iPhone hacker who unlocked the phone. 

This software will enable you to install third-party software that Apple does not like [not approved from Apple's App Store]. There is only a Windows version available for the jailbreak, Mac version is coming soon.

Steps to jail break is given as follows :

1. You need a Windows PC [Does not work with windows 7]
2. Download and install the  latest iTunes
3. Download purplera1n and run purplera1n [You will see a windows icon, click that to download the software to jailbreak]
4. Test your patience -  Wait
5. Run Freeze
6. Reboot the iPhone

You have successfully JailBroke the iPhone now

Note:  Cydia doesn’t display after running Freeze, make sure you reboot.

[Image credit: http://www.purplera1n.com/]