How does one handle two-body job searches? One thing I've heard conflicting advice on is how to handle a job search for two people simultaneously; especially the strategy of things like: when do you mention your situation to the departments in question? In your cover letter?  When you're invited to an interview?  At the interview?
As usual, people should be specific about what kind of institutions and which nations they have in mind with their advice.  Also, presumably strategy differs a bit depending on whether the second person is a mathematician, or in a different discipline; it would be great to hear about both of those cases.
 A: It's important to know that if you want to discuss this with the chair of a department where you're interviewing, or have an offer, you will have to bring it up yourself; it's illegal (at least in the U.S., or at least in the states I'm familiar with) for a university to ask you about your marital status.  You'll find that most departments are eager to help to the extent they can, and that there's wide variation in what that extent is.
Update:  Based on the comments below, let me add that some chairs don't know what the law is, or don't care; so it's clearly not universally true that you won't be asked about your spouse.  
Maybe I'll also add that, if I remember right, I never brought up my spouse until I had an offer.  The interview stage is when you're trying to convince them that you should work there; the post-offer stage is the reverse.  The problem with bringing up spousal issues at the interview stage is that the department may start thinking "We're never going to find a job for her husband in post-Inca ethnography, so maybe we should make an offer to somebody we're more likely to get."  I think this would be somewhat unethical, but then again so is illegally asking you about your marital status, and it's sometimes done.
So the difficult question:  what to do if you don't want to talk about your two-body problem at the interview, and you're asked about it?  On general "keep the tone light" grounds I would advise against saying "You are breaking the law."  If you said, "I'd rather keep this just about me for the moment," I would be fine with it; but for the sake of honesty I should say I'd expect some chairs would find it weird.
Perhaps the best thing would be to concede that you have a spouse, and to say something about what field they're in, but to play down any sense of a two-body "problem."  If the spouse is an academic (which I think is the situation in the posted question), I think it is totally OK to create the impression that a TT job for your spouse would be a big draw, but not a necessity.  This allows the math department to get the ball rolling on an attempt to do a double hire, but reduces the risk that the department will find out there's no job for your spouse and give up on you, too.
Note that the advice above only applies if you're (illegally) asked about your spouse in the interview.  If you choose to bring it up yourself, I think you should be totally upfront about what will be required to hire you.  If you are deadset against considering anything other than a double TT offer (e.g. if you are already situated in a place where you have one TT and one non-TT offer) then you should go ahead and bring this up to avoid wasting anyone's time. 
A: I am not entirely sure what you should do.  But, at least at many American math departments, I can make two suggestions for what I wouldn't do:


*

*Don't try to keep it secret for as long as possible.  Sane math departments want to help with two-body problems.  But it takes real work to help, and the department can't take do any of that work until you define the problem.  It could be a mistake to be very forward about a two-body problem, as if to suggest that that's supremely more important than research and teaching.  One deft move which is I think is fine is to have a link to your partner toward the end of your home page, without an explicit statement that you have a two-body problem.  Also, you have to define your two-body problem privately to each university when the time comes; what you say on your home page is not enough.  (As Jordan Ellenberg says below, it's outright illegal for the university to infer your romantic status or even ask you.)

*Certainly if you are both in math, don't interview on the same plane trip.  It's important to establish that you and your partner are independent professionals.  The department has the right to schedule you on the same plane trip and I wouldn't say that you should draw a line in the sand if they do.  But it's better for both sides to avoid this.

A: There was a piece about this in a recent issue of the Notices of the AMS.
I've found this too: Solving the Two-Body/Dual-Career Problem 
A: Preemptive disclaimer: I am one mathematician, and this is only my experience. That experience is based on applying to tenure track positions at major American research universities, and being male. 
My wife works as a clinical research assistant, meaning that she runs experiments, files paperwork, recruits subjects and applies for grants, but she is not an academic and does not do her own research. She currently works at a hospital with a major research program; she has worked in university labs in the past.
My pattern, based on the advice of several older mathematicians, was to omit my wife from the paper applications but mention her early in the interview process. At times I brought this up when the chair first called me; more often I brought it up at the beginning of our face to face interview. My thinking was that I would not go anywhere that my wife could not find work, so it would be best to bring this issue up head on and find out how the university would respond.
Everywhere I did this, I received a very positive and supportive response. Chairs and deans promoted the opportunities for my wife in their campuses and cities, and offered help in finding work. I did not try to get a commitment that my wife would be hired by the university, because my understanding is that it is not reasonable to ask for that sort of commitment for a nonacademic position, but I did attempt to determine whether it was likely she could find work at or near the university.
A: I have found a page on "Resources for academic couples" here:
http://astro.swarthmore.edu/~jensen/couples.html
