Unlocking: An iPhone comes locked to a particular carrier (AT&T) in US. To use the iPhone with any other carrier you need to unlock the phone.
Jailbreaking: By default, you can install applications on the phone only through the iTunes App Store. Jailbreaking allows you to install any application and tinker with the iPhone to your heart's content.
Baseband: The low level software which deals with making calls and other cellular network related stuff. Without this working correctly your iPhone will be just an iPod Touch. Go to Settings -> General -> About -> Modem Firmware to know your baseband version.
Firmware: The iPhone OS software. The latest version will be version 3.0 which will be released on June 17th. The version before that was 2.2.1. When you connect your iPhone with iTunes, you can see the firmware version in the Summary Tab. iTunes will list the Name, Capacity, Software Revision and Serial Number. Software revision is your firmware number. You can download firmware files from Apple and the files have the 'ipsw' extension.
Software Unlock: The iPhone dev team regularly releases software unlocks for iPhone. They even have the unlock ready for OS 3.0. The software unlock will work with only specific devices so it is entirely possible to have an unlock for iPhone 3G running OS 3.0 but not for iPhone 3G S running 3.0. For unlocking the phone through this method, you first need to jailbreak it. iPhone Dev team releases two tools for this QuickPwn and PwnageTool. QuickPwn will jailbreak an official firmware version and Pwnagetool will allow you to create custom firmware. You will need to use PwnageTool. As of now (June 17th), if you have updated your iPhone to firmware version 2.2.1 and baseband version 02.30.03 you cannot unlock it. This will change with OS 3.0.
According the dev team the unlock (ultrasn0w) will be available on June 19th and the jailbreak should be available soon. So if you don't want the unlock now, you can go ahead and install OS 3.0.As always check the iPhone Dev Team Blog and download the tools only through the iPhone Dev Team official torrents. After jailbreaking your iPhone you will need to install yellowsn0w (ultrasn0w for OS 3.0) to unlock the phone. Here is a step by step guide to jailbreaking the iPhone using PwnageTool. The instructions are meant only as a rough guide. You should also check the requirements on the dev team blog before attempting an unlock.
Hardware Unlock: The baseband chip can be reprogrammed with an altered baseband firmware which removes the locking code. This unlocks the phone but does not jailbreak the phone. Currently works with 2.2.1 if you can find someone who offers the services. Whether this hack is compatible with OS 3.0 or whether you will be able to unlock it again after upgrading it to 3.0 is not known at this moment. Also this is the most invasive of all the unlocking methods and there is a high chance of your iPhone becoming toast.
Proxy SIM: This thin circuit sits on top of your SIM and iPhone will accept it as it were a locked carrier's SIM. You may experience a deteriorated call quality and overall stability with a proxy SIM. You can find sellers of Proxy SIMs on ebay.
Unlocking/jailbreaking your iPhone will void your warranty if you take the unlocked/jailbroken iPhone to Apple Customer Service Centres. So if you have an unlocked/jailbroken iPhone you will need to restore the iPhone to its original firmware. Also unlocking/jailbreaking via Software Unlock or harware Unlock can potentially render your iPhone useless, so be aware of the risks before you do this.
Update 1: iPhone Dev Team has released jailbreak for OS 3.0 but not the unlock (ultrasn0w). But this will not work with iPhone 3GS. If your phone is currently unlocked via Yellowsn0w updating to OS 3.0 and jailbreaking will lock the phone