As above, just out of morbid curiosity. Do the websites of individual airlines have APIs for these engines to exploit? Or do you write programs to navigate individual websites and provide inputs (origin, destination, dates of departure, return) and obtain the outputs (price, time etc.)?
Edit: Ok just found this after I submitted question. Still, would be interested in looking at how its done programatically. Say in Java, what kind of libraries would be good for this?
There are several ways to get such information. The best (and most reliable) would be to contact the airlines you're going to be dealing with. Many if not most will have public APIs for accessing their reservation system, allowing users to request quotes for flights, seat availability, and make reservations. Of course usually that will require a contract between you and the airline telling you how you can use the information, and for bookings you're going to probably need another contract with them to handle payments, kickbacks, etc.
Such APIs can be "modern" SOAP systems, or more old fashioned things like EDI, EJB calls, or whatever but the principle remains: you ask for something, their servers give the requested information.
Less ethically correct, harder to implement, and far more fragile you could try screenscraping their reservation engines. But the screen layout of those of course change regularly :)