I would second the part about getting to know the travel policies. I didn't get a huge amount of travel when I was working for a big company, but they'd have tons of edicts and their own in-house travel agency (contracted with Carlson, I think) for bookings.

You could go rogue, but if it cost more you'd get flagged and they sent reports to your department head. I was usually on the right side of things...one time I booked a CO connection to ROC that cost maybe $8 more but brought in a $50 Entertainment coupon that was good on the ticket!

You could also be a hero by staying over a Saturday night before or after if it got a lower fare. I do remember once that I booked TWA for ATL-TPA-MIA and v.v. and got a comp first-class upgrade on MIA-TPA (even with no status at all) and they went bonkers at first, saying I needed VP approval (they calmed down when they saw it didn't affect the fare, which was sub-$200)