The answer is, it depends. Generally, firmware upgrades can

1. Correct flaws in the original firmware. For instance, if there were a metering mistake in the original firmware, that can get fixed.
2. Expose new software functionality. I'm thinking of CHDK here, that brings new functionality to canon powershot cameras (such as RAW shooting, timed shooting, etc). For whatever reason, sometimes camera manufacturers leave out capabilities from their cameras that the camera can physically perform. These kinds of upgrades can expose that functionality.

Importantly, firmware upgrades cannot add capabilities that the camera doesn't already have physically. Firmware upgrades cannot increase megapixel count, lens characteristics, etc.

Finally, it's also possible for firmware upgrades to introduce new bugs. These things are software, and as such, still need to be subjected to testing and debugging. You may see multiple firmware upgrades for the same camera if one patch introduces a bug and another one removes it.

As for firmware upgrades that can improve performance, the one that comes to mind (other than CHDK, which really exposes functionality) was Sigma's upgrade for the DP2 camera. The most recent upgrade reduced the lag of the autofocus algorithm in lower-than-sunlight light levels (though the camera still suffers in low light).