I got a iPhone 3GS from my friend's girlfriend who has never upgraded her phone since she got it at 3.1 firmware 05.11.07 baseband...I'm trying to upgrade her phone to 4.0 or 4.0.1, but theres no way I can figure this out...I tried jailbreakme.com and it says the firmware is too old...I need help guys

Check the bootrom version via DFU mode. This phone is likely old enough to be old bootrom.

http://theiphonewiki.com/wiki/index.php?title=Bootrom

iBoot-359.3 "old bootrom"
iBoot-359.3.2 "new bootrom"
If it is old bootrom

Make sure you have iTunes 9.2 or newer installed.
Sync/backup with iTunes.
Do initial jailbreak with blackra1n rc3. This is just to pwn the phone - I would never recommend using blackra1n as a primary jailbreak.

Then use pwnagetool 4.0.1 to make a custom iOS 4.0 ipsw and follow the instructions to restore.

Because you used blackra1n to pwn, u can answer yes when pwnagetool asks if your phone has been jailbroken/owned before.

If you only have access to windows - I recommend you try and find a mac to borrow. Otherwise you can try sn0wbreeze but we refuse to support or recommend sn0wbreeze as it is a poor quality windows copy of pwnagetool

Otherwise you need a SHSH saved on cydia or on your own computer to restore to official 4.0 - apple no longer allows this. They only sign 4.1 restore now. Don't restore to 4.1 as you'll lose the option to jailbreak and unlock - maybe for ever!