Water softener trips TPR valve
Dealing with that pesky urge to...expand

Your issue is that the water in a hot water heater expands as it is being heated.  This backpressure is normally taken up by the city water supply without issue, as the water in the heater is all still potable (drinkable), and most houses have nothing in their water supply line that would block this backflow of water.

However, some houses have a device on the cold side of the hot water heater that blocks this backpressure, at least some of the time.  While the usual culprit is what's called a pressure-reducing valve or PRV, and devices known as backflow preventers also pose this problem when fitted, in your case, the behavior is caused by the water softener shutting off its outlet valve during the regeneration process.  With nowhere to go, the water in the tank builds up pressure as it is heated, and eventually the T&amp;P valve on the water heater lets go to relieve this excess pressure down the drain.

Fixing this requires adding an expansion tank in between the water softener and the water heater.  This provides a place for the extra volume occupied by the heated water to go, thus mitigating the pressure change and keeping the water heater relief valve from opening in the process.

While you're fixing this plumbing...

There is another fix you need to make to your water heater while you are in re-working the plumbing. Since you have softened water plumbed to your heater, which is highly conductive, your heater's protective anode rod (sacrificial anode) will not last long, as the extra conductivity of the water makes the rod excessively active.  And once that rod goes away, there is nothing standing between your water heater tank and rusting away into a giant leak; while typical residential water heater tanks have a thin porcelain-glass lining that acts as primary corrosion protection, this lining is expected to have defects in it that allow water direct access to the tank steel.

This is fixed by removing the anode rod from the tank and installing a powered anode in its place.  Instead of forming a galvanic cell between the tank steel and the anode rod with the water as the electrolyte to prevent the tank from rusting out, the powered anode converts 120V AC into a small, low-voltage current that is impressed on the tank steel (it's a household version of something called impressed current cathodic protection in industry), thus opposing the normal galvanic cells that drive the corrosion process and keeping the tank's steel intact for as long as power is applied, irrespective of water conductivity.

As to finding one? Powered anodes are available through a variety of sources; Amazon has the Corro-Protec kit available for just over $100, while your local supply house may have the Corro-Protec or Ceranode kits available; if those don't work, you can get powered anodes through Water Heater Rescue.  If you have an A.O. Smith-made water heater, and it is still under its factory warranty, you can get a powered anode kit from A.O. Smith (part number 100305721) that is guaranteed to not void the remaining warranty on the heater, even.

In the case the heater's already shot

There is a chance, of course, that your water heater has bigger issues than needing the aid of a mere expansion tank.  Some blundering types pull the anodes out of water heaters used on softened water, and this leads to a very short life for said water heater before it dies a messy death from the inside out.  It could also be the case that the existing heater may be at the end of its natural life and in need of replacement anyway.

In either of those cases, I would recommend looking to either an A.O. Smith-made water heater with one of the aforementioned powered anode kits fitted for your replacement heater if you wish to stay with a traditional glass-lined tank, or looking quite hard at alternatives to glass-lined tanks.  Stainless steel tanks are a fairly popular option, but take some care in material selection, especially in water with a high chloride content, due to issues with stress corrosion cracking in the most common grades of stainless steel.  There are also cement-lined water heater tanks out there, if stainless steel is not an option in your case; however, they are harder to find than stainless tank heaters are.  Lastly, if you are replacing an electric water heater, Rheem makes a polymer-tanked electric water heater called the Marathon that has no issues with corrosion whatsoever.