How were transaction fees determined before the change and after the
The fees were determined on the person sending the bitcoin, or the client in many cases. One can send a tx with no fee, but it has lower priority to get included in a block. They are still determined the same way. The "default" method for determining the fee is generally 0.000055 BTC/1kB. Technically, the fees help determine the priority for a transaction to get included in a block. The formula is: priority = sum(input_value_in_base_units * input_age)/size_in_bytes, therefore, it is a function of a few variables.
How does this change affect third-party software developers (who do
not use Bitcoin-Qt wallet) - do they need to mimic this change?
The change needs to be implemented in wallet software that determines the transaction fee for the user (i.e. Multibit), or changed in a setting by the user (i.e. qt client).
How does this change roll across the network? Do 51% of miners need to update to the new version before the change starts to be effective?
The change rolls across the network as the miners update their qt client to the version with the updated protocol rules, otherwise, they will mine and still play by the rules in the old client. This change doesn't necessarily require 51% of the network to adopt the new version for the lower tx fees to take effect. Theoretically only one miner would need the new version and solve a block with the client for the new tx fee rules to take effect for that block. If one uses the lower tx fees while few miners have updated their clients, the fee will be considered low, and probably would be lower than lots of current transactions, so would be placed further down in the queue. If the update is done by a few major pools, the change would be effective, although using the new tx fee might cause a slight delay if a block is solved by a miner with old client and the block is full of transactions with higher priority.