UPS for sure has been doing fuel surcharges for years.. We can thank trash airlines like skybus for hurting the majors and forcing them to keep their costs down. LCC's like Jblue, SW, Air Tran, Skybus and the likes are hurting this industry. SW got lucky with fuel hedging (very smart too..but they didnt' know it was going to get this bad, no one did).
If the airlines try to take more concessions from labor, Doodie will hit the fan, it wont be pretty.