There was only one time that Apple changed hardware on an iPhone that was already being sold. The 3GS came out in June 2009 and the "new bootrom" models went into production shortly thereafter and came out around September 2009. This was an attempt by Apple to thwart jailbreaking. Since the hardware was changed, the boot portion of the current jailbreaks didn't work on them. 3.1.2 came out in October. People who bought their 3GS' a few months after the phone came out had to boot their jailbroken iPhones from a computer since the untether didn't work on the new hardware. This is known as a tethered jailbreak. We've had some variations of it since then, including semi-tethered jailbreaks.
You have to read carefuly, when you jailbreak, there are warnings on Cydia that tell you not to update, etc. in order to preserve the jailbreak. Yes, you would have to jailbreak again to use any of the jailbreak software as you need Cydia to reinstall.