If this helps ANYBODY then great! I just know I was super frustrated trying to find any information on this, so I felt the need to type out what I did to make it work so people can read it, and so that I have it if I need it in the future. 
Jailbreaking and Unlocking Iphone 3gs iOS 5.1 to work on a prepaid Sim card. (tethered) for Windows.
If you have an iphone and you have purchased a prepaid Sim card, such as Petro-Canada or SpeakOut, this may help you. I am not guaranteeing anything, just sharing my experience with getting it to work.
I had received the iPhone 3gs from my sister, not jailbroken or unlocked, on the Bell Network. I am a total newbie when it comes to stuff like this, so dont mind me if I use non-computer-nerd lingo. I went into a Petro-Canada gas station and asked for the Sim card they sell there. It was $15. I set it up online with my chosen plan (100 talking minutes a month, unlimited texting and unlimited web browsing came out to $28 a month). The packaging stated that it would work with any unlocked phone. I knew my iphone wasnt unlocked yet, but I put the Sim card in anyway (if you look on one end of the phone theres a tiny little hole you can stick a pin into and it just pops right out) it said invalid sim card in the corner. So I set out to jailbreak and unlock the phone.
First you must jailbreak the phone. I paid for the help of a website called IphoneTrump. I ended up not using any of its services or downloads, so essentially it was a waste of $19 dollars, but trying to get that website to work is what taught me what I needed to do to jailbreak my phone, so not a total waste in my opinion. The website required me to restore my phone to iOS 4.2.1. The website gave me a download link to Redsn0w which I downloaded. It also gave me the firmware download to restore my phone down to iOS 4.2.1. I opened itunes and by hitting shift and restore, and clicking on the 4.2.1 firmware I had downloaded, it appeared to start its restore. After a minute or so, it came up with an error message (error 3195). I tried over and over again and could not get it working. I searched every forum and youtube video. I tried everything to get it working (changing hosts file, etc) and nothing worked. In the end, I decided I would have to find a way to jailbreak it on its current firmware.
Here are the steps to jailbreak your iphone iOS 5.1.
Tethered Jailbreak for iPhone 3GS iOS 5.1
Download firmware iOS 5.1
http://www.iphonetechie.com/download-section/firmware-downloads/
Now download Redsn0w 0.9.10beta6
http://osxdaily.com/2012/03/08/redsn0w-0-9-10b6-download/
Plug your iphone into your computer and open redsn0w. Hit jailbreak. When it asks you to browse for your firmware, choose the firmware 5.1 you downloaded. Follow the instructions, be sure to select Install Cydia and the baseband option (sorry I forget the exact wording for the baseband option..) when you are done you will need to keep your phone plugged in and turn it off. This is a tethered jailbreak, meaning the ONLY way you can turn your phone on is if you plug it into your computer and boot it using redsn0w. (unless you want to lose all your jailbreak info as well as Safari) Hit extras and choose the boot option. Follow the instructions (it will instruct you to put your phone into DFU mode.. it will look like your phone wont turn on.. dont worry, just keep following the instructions). When Redsn0w is finished the boot, your phone should now be jailbroken and have Cydia installed on your springboard. Now lets continue onto the unlock steps..
Unlocking
1.) Launch Cydia Installer by selecting Cydia from your SpringBoard.
2.) Press the Manage button at the bottom of the screen.
3.) Press the large Sources button.
4.) If the ultrasn0w repo is not present, press the Edit button at the top right of the screen, otherwise, skip to step 9.
5.) Press the Add button at the top left of the screen.
6.) Enter http://repo666.ultrasn0w.com/ as the source URL and press the Add Source button.
7.) Once the source has been added press the large Return to Cydia button.
8.) Press the Done button at the top right of the screen.
9.) Press to select repo666.ultrasn0w.com from the list of user entered sources.
10.) Press to select ultrasn0w from the list of packages.
11.) Press the install button at the top right of the screen.
12.) Press the Confirm button at the top right of the screen.
13.) After installation completes successfully, press the large Return to Cydia button
14.) You should now be able to inser the SIM of your choice!
If the internet on your new sim isnt working.. (this worked for my Petro-Canada plan)
You will need to adjust the APN menu on your iPhone. Using your iPhone with a wifi connection, open Safari and go to http://www.unlockit.co.nz with the iPhone. Follow the websites instructions, (for me I had to select Canada and Petro-Canada) and the wesite should do the rest. When it is finished, plug your phone (while it is on) into your computer, turn it off and do a boot using Redsn0w. When your phone turns on again, everything should work!
Goodluck!
Allie Geiger
Jailbreaking and Unlocking Iphone 3gs iOS 5.1 to work on a prepaid Sim card. (tethered) for Windows.
If you have an iphone and you have purchased a prepaid Sim card, such as Petro-Canada or SpeakOut, this may help you. I am not guaranteeing anything, just sharing my experience with getting it to work.
I had received the iPhone 3gs from my sister, not jailbroken or unlocked, on the Bell Network. I am a total newbie when it comes to stuff like this, so dont mind me if I use non-computer-nerd lingo. I went into a Petro-Canada gas station and asked for the Sim card they sell there. It was $15. I set it up online with my chosen plan (100 talking minutes a month, unlimited texting and unlimited web browsing came out to $28 a month). The packaging stated that it would work with any unlocked phone. I knew my iphone wasnt unlocked yet, but I put the Sim card in anyway (if you look on one end of the phone theres a tiny little hole you can stick a pin into and it just pops right out) it said invalid sim card in the corner. So I set out to jailbreak and unlock the phone.
First you must jailbreak the phone. I paid for the help of a website called IphoneTrump. I ended up not using any of its services or downloads, so essentially it was a waste of $19 dollars, but trying to get that website to work is what taught me what I needed to do to jailbreak my phone, so not a total waste in my opinion. The website required me to restore my phone to iOS 4.2.1. The website gave me a download link to Redsn0w which I downloaded. It also gave me the firmware download to restore my phone down to iOS 4.2.1. I opened itunes and by hitting shift and restore, and clicking on the 4.2.1 firmware I had downloaded, it appeared to start its restore. After a minute or so, it came up with an error message (error 3195). I tried over and over again and could not get it working. I searched every forum and youtube video. I tried everything to get it working (changing hosts file, etc) and nothing worked. In the end, I decided I would have to find a way to jailbreak it on its current firmware.
Here are the steps to jailbreak your iphone iOS 5.1.
Tethered Jailbreak for iPhone 3GS iOS 5.1
Download firmware iOS 5.1
http://www.iphonetechie.com/download-section/firmware-downloads/
Now download Redsn0w 0.9.10beta6
http://osxdaily.com/2012/03/08/redsn0w-0-9-10b6-download/
Plug your iphone into your computer and open redsn0w. Hit jailbreak. When it asks you to browse for your firmware, choose the firmware 5.1 you downloaded. Follow the instructions, be sure to select Install Cydia and the baseband option (sorry I forget the exact wording for the baseband option..) when you are done you will need to keep your phone plugged in and turn it off. This is a tethered jailbreak, meaning the ONLY way you can turn your phone on is if you plug it into your computer and boot it using redsn0w. (unless you want to lose all your jailbreak info as well as Safari) Hit extras and choose the boot option. Follow the instructions (it will instruct you to put your phone into DFU mode.. it will look like your phone wont turn on.. dont worry, just keep following the instructions). When Redsn0w is finished the boot, your phone should now be jailbroken and have Cydia installed on your springboard. Now lets continue onto the unlock steps..
Unlocking
1.) Launch Cydia Installer by selecting Cydia from your SpringBoard.
2.) Press the Manage button at the bottom of the screen.
3.) Press the large Sources button.
4.) If the ultrasn0w repo is not present, press the Edit button at the top right of the screen, otherwise, skip to step 9.
5.) Press the Add button at the top left of the screen.
6.) Enter http://repo666.ultrasn0w.com/ as the source URL and press the Add Source button.
7.) Once the source has been added press the large Return to Cydia button.
8.) Press the Done button at the top right of the screen.
9.) Press to select repo666.ultrasn0w.com from the list of user entered sources.
10.) Press to select ultrasn0w from the list of packages.
11.) Press the install button at the top right of the screen.
12.) Press the Confirm button at the top right of the screen.
13.) After installation completes successfully, press the large Return to Cydia button
14.) You should now be able to inser the SIM of your choice!
If the internet on your new sim isnt working.. (this worked for my Petro-Canada plan)
You will need to adjust the APN menu on your iPhone. Using your iPhone with a wifi connection, open Safari and go to http://www.unlockit.co.nz with the iPhone. Follow the websites instructions, (for me I had to select Canada and Petro-Canada) and the wesite should do the rest. When it is finished, plug your phone (while it is on) into your computer, turn it off and do a boot using Redsn0w. When your phone turns on again, everything should work!
Goodluck!
Allie Geiger