Does iPhone's baseband change when updating iOS?
Q: Does it change when updating iOS?

A: Yes, the firmware is revised and is packaged inside the software update archive.

Q: Do all iPhones have the same baseband?

A: No. They get updated and iPhones can have one of multiple chips with incompatible firmware.

Q: If not, how do they differ?

A: Bugfixes, security patches etc. Different generations have differing chipsets as well.

Q: And ... can I unlock an iPhone 4 with iOS 5.1.1?

A: Yes, you can use ultrasn0w for a software unlock if your iPhone 4's baseband is 01.59.00. You can check your baseband version by going to Settings->General->About and looking at the Modem Firmware number.

Sources: 

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

http://www.engadget.com/2012/06/04/ultrasn0w-unlock-iphone-4-3gs-ios-5-1-1/

iPhone 4 Chipset Page: http://theiphonewiki.com/wiki/index.php?title=XMM_6180