Jailbreak iPhone OS 4.0 (iOS 4.0) using redsn0w on PC / Mac
Create a folder on your computer called Jailbreak. Download redsnow 0.9.5b5 by the iPhone Dev Team from here - redsn0w for iOS 4.0 and extract it into the Jailbreak folder.
Next, download the official firmware IPSW from Apple's site and place it in the same folder. It's a 292 MB download. Download it here - Firmware 4.0 IPSW
Download iTunes 9.2 and install it. Connect your iPhone 3G or 3GS to the computer and launch iTunes.
Select your device from the left tab. Press the Shift key and click on the Restore button. Go to the Jailbreak folder you created and select the firmware IPSW you downloaded from the Apple site.
After your iPhone has been updated with the restore IPSW, open the Jailbreak folder again and click on the redsn0w application we extracted earlier. Click on the Browser button and select the firmware IPSW we downloaded to the Jailbreak folder.
After the IPSW has been identified, click Next.
redsn0w will now begin the jailbreak process and give you a list of options to choose from. Choose the options you want - Do tick the Install Cydia button and enable Multi-tasking, Homescreen, Wallpaper and Battery percentage. Verbose boot shows you all the details while booting. You can also select custom boot and recovery logos - they should be PNG images in RGB or grayscale with dimensions of 320 x 480 pixels.
Switch off your iPhone and connect it to the PC. Follow the instructions on the screen to get into DFU mode.
Press both the Power and Home buttons simultaneously for 10 seconds. After that, release the Power button but keep the Home button pressed for 30 seconds.
redsn0w should now detect the device. The jailbreak will start and your device will be rebooted. After the jailbreak has been completed, click on the Finish button and start your iPhone. You should see the Cydia icon on the menu.
The steps are almost the same if you use a Mac.
To unlock iPhone 3, iPhone 3GS and iPhone 4, read the following tutorial: How to Unlock iPhone?