When I worked at Ernst & Young out of college, I remember a manager at our orientation who was going over the travel policy summed it up as: "You should always be able to do your job. You should never have a personal profit or loss from company travel."
I now work at a company of about 400 employees where many people travel, and we have no formal travel policy. Our CEO asked me to come up with one a couple years ago, so I wrote one out (I figured he would edit some things down, like F is OK on flights over 4 hours) but he just said thanks and that was the last I'd heard until one of our VPs mentioned he'd seen it and was impressed.
It really depends on the company and on your seniority. My friend the public company CEO flies paid business (well, he said he was losing his UA Global Services because he's flying on the company jet too much...boo hoo) and stays at the W or Westin most times I think.