Bicycle Touring Pro has a good page with major airline policies laid out. It is from 2008, so perhaps a bit out of date, but a good starting point.
This summer (2012) my wife and I flew with our bicycles from San Francisco to Dublin, rode around Europe for the summer, and flew back from Copenhagen to SF. We used British Airways, and they were complete rock stars about it. Free, no hassles. My bike has Ritchey Breakaway couplers in it, similar to (but better than, IMHO) S&S couplers. But I just left it together because it was more of a hassle to have to deal with the Ritchey case at our destination and the additional disassembly/reassembly.
In Dublin, we put our bikes together in the airport, discarded the boxes there, and rode off on our trip. We mailed the packing material — pipe insulation, dummy axles — to a friend in Copenhagen, which just cost 10 euros or something. If you do this, however, make sure you let your friends know it is coming. We didn’t, and our friends (my wife’s relatives actually) almost threw it out because they thought it was a joke, or that some “actual” item we were mailing was stolen in the mails.
At the end of the trip, in Copenhagen, we just took our bikes to a bike shop near the airport to have them pack them. It cost $60 per bike or so, but it was easier than schlepping a box on the metro twice (once from the shop, again to the airport), and we had another day to be tourists in Copenhagen. The bike shop was 2 miles from the airport and drove our bikes there as part of the deal.
To avoid having to pay for a second checked bag — BA only allows one checked “bag” per person, which was the bikes — we stuffed panniers and other gear into the boxes to the limit (23 kilos, I think), and each took a pannier as a carryon.