I installed a Gear Vendors overdrive in my 96 in April 97 at 14000 miles. The truck now has 106000 and this unit has been trouble free except for one shift solenoid failure.
There was no noticeable change in fuel mileage.
Split shifting is great when pulling a load. The only disadvantage is the slow shsifting at low speeds, but you can learn the timing.
Also nice is 80 mph at ~1800 rpm.
Bought direct from Gear Vendors, my total cost for the installation was about 2200, but I work cheap.
I had no warranty problems, rear axle was replaced under warranty in 98.
Also consider the US Gear overdrive. I see from their website that it will now do aplit shifting.
My 96 is in the TDR classifieds, if you want to buy the overdrive with a truck attached!