How can I update and jailbreak/unlock my iPhone 3Gs from 4.1 to 6.1.3?
The first thing you should note is that Ultrasn0w hasn't been supported for a very long time. You should find yourself a "grey-market" unlock (on eBay or various other sites) or contact the phone's original carrier (probably AT&amp;T).

Once you have your phone factory unlocked, plug your phone into your computer and hold down the Home and Power buttons for about 10 seconds. Let go of the Power button but keep the Home button held down. This places the phone in DFU (Device Firmware Upgrade) mode. iTunes will tell you that your phone needs to be factory reset, and you should go through the normal process. Since iOS 6.1.3 is the latest version available for the 3GS, you don't need to do any tricks here.

From that point, you can jailbreak with whichever tool you like.