My husband and I have just (May 2000) completed our two-body academic search in CS. Here are a few additional comments based on our experience. For context, when we started searching, my husband wanted a faculty position in a top 20 research department. I was debating between top liberal arts schools and good (rank 30-45ish) research universities; I was also willing to consider industrial positions in my research area if needed to solve the two-body situation.
We mentioned our two-body situation in our cover letters for departments that we both applied to. If there was only school in the area, we said that we both needed jobs at that same department. If there were multiple options, we mentioned that the other had applied to the same department and we needed positions in the same area. We chose this approach as we knew we would not take positions that couldn't accommodate both of us.
Having finished the search, we feel this strategy was a mistake. We should have left our two-body situation out of the letters, mentioning it only when one of us received an interview call. This is for two reasons:
Interviews are partially about visibility, especially if you are trying to get a job in the top 20. Having interviews at some top 20 places affects how other top places view you. If one of you isn't really at the level of a top place, tying your applications together may hurt the other one's chances of getting an interview, which could hurt that person's chances for interviews at other top places that might solve your two-body problem.
It cost us flexibility. Part way through the process, our chances of getting good options in the same city appeared slim (the situation improved considerably later in the season). At that time, I began to consider applying for a wider range of industrial jobs. Given that, we discussed trying to sever our applications at certain schools that were academically isolated and hiring in my husband's area but not mine (we eventually chose not to do this). Keeping the applications separate from the start would have avoided this problem.
We intentionally split our interviews at common schools so that one person interviewed early (to check out the department) and the other late. We did this to prevent schools from making two early offers and then pressuring us to accept them before we could finish most of our interviews. For research schools, this strategy worked well. However ...
A two-body search in which one person wants a top research university position and one wants a small school (liberal arts or similar small school) are extremely difficult due to differences in interview schedules. I had offers from small schools that required responses before my husband's schools in the area had finished reviewing applications. There was no way the small schools could have waited for my husband to interview, much less for his schools to make decisions. Furthermore, we found many schools unresponsive to queries about his application status, even once we explained my situation. In the end, we managed to get a research university position for him and a small university position for me, but this was mainly because the chairman at my school knew us both well and was willing to delay their process as long as possible (they finished interviewing well over a month before my husband's department did). I doubt this would have worked out otherwise.
Buy a pair of them. It's well worth the cost. From an interview standpoint, cell phones make it easy to reach host departments when you miss connecting flights, etc. From a relationship perspective, cell phones were invaluable for staying in touch. We saw each other in person for no more than 3 consecutive days at any time from early February until late April. At one point, we didn't see each other for three consecutive weeks.
With the phones, we could check in each night, trade impressions of departments, and correlate questions to ask of each school. We never had to track where the other person was at any time. I doubt we could have had such detailed conversations had we saved them all for times when we were physically together.