Short answer: Yes-ish
Long answer: Depends on what exactly you mean "change the software", what mobile phone you are using, how worried you are about bricking your phone.
If you mean run a totally different OS on your phone (i.e. Android on a WinMobile or iOS on an HTC) then no. [having said that there are some exceptions to this rule, but it is generally alpha level software and very crashy]
If you want to customise the version you are running, it's perfectly possible. Android phones for instance have loads of custom versions of the OS, I for instance can run the HTC Desire Sense UI on my Goggle Nexus One. Some android phones that come with 1.6 have had 2.1 hacked onto them.
iPhones you can upgrade to the new version of iOS, though you won't nesecarilly get all the new features on older phones as they lack certain bits of hardware.