In my youth, I thought that being smart and doing well in research and/or teaching should be enough to get you a job. Maybe this was once close to the truth, but now you have to compete with hundreds of other applicants, most of whom are also promising mathematicians. While doing good research and/or teaching (depending on the job) is still the most important thing to getting hired in academia, I'm going to emphasize the other things you should do to get a job, though I'll discuss some aspects of research and teaching as well.
This is aimed at grad students and postdocs in math who want to pursue careers in academia in the US, though I imagine much of this is applicable to other academic situations. Furthermore, I primarily have in mind the goal of getting a tenure-track position, though don't blame me if some of this advice helps you get a postdoc also. (By "postdoc" here I will mean a temporary post-PhD academic position, not all of which are technically called postdocs---they go by various names such as visiting assistant professorships, non-tenure-track assistant professorships or instructorships). The whole essay is meant to be read years before you plan to apply for tenure tracks, though some of it may still be helpful to people who are applying now. (Even the sections on Applications and Interviews discuss things you should do far in advance of applying.) If you're looking for an advisor, see here.
A word of caution: Some the advice I'll give here may sound an awful lot like "don't poke yourself in the eye with that stick." Well, if I say it, you can be sure it's because I saw someone poking themselves in the eye with that stick. Putting a stick in your eye can be easier than you think, especially if you're looking the other way at the time. (By the way, don't actually poke yourself in the eye with a stick to test this. See, I bet you were about to try it, weren't you?)
Special thanks (apologies?) to: Jennifer Beineke, who selflessly read through 18 pages of advice she didn't need to hear (did I mention this is needlessly long? you're welcome), and explained to me what liberal arts schools (at least hers) really look for. She also wrote up some excellent slides on this topic, linked to in the list of resources at the end.
You're likely to get all sorts of career advice from different sources, and different people will give you conflicting advice. In fact, I will manage to give you conflicting advice all by myself. The truth is, many things you do will make your application look better to one person and worse to another. There is a lot of subjectivity in reviewing applications, both across different schools and within faculty at the same school. You want to try to make your application have enough good points to get noticed at the kind of schools where you want to get hired, and avoid anything that will make these schools throw your application right out. So you should try to get advice, particularly when you have specific questions, from people whose opinions you trust and are well informed on what hiring committees at your target schools want to see.
Probably the most important advice I have for you is: start thinking about how to make yourself a strong applicant early. Too many people wait till the Fall they are applying to get advice about job applications, by which point they don't really have time to do anything to make their applications stronger. This is not as big of a deal when you're applying for postdocs as it is for tenure-track positions.
Even when it comes to the Fall that you apply, many people don't get their act together on time, and miss some of the earlier deadlines (e.g., the NSF Postdoc or deadlines for the Joint Meetings), or don't give their letter writers enough time. In fact, it's best to get your applications in early. Many professors will start looking at applications before the deadline, and if they get excited about your application before they see too many others, your application will have more momentum going into the decision process.
Applying for jobs is stressful, and very few of us get exactly the job we want. However, the more flexible your attitude going in, the less stressful the process should be for you. I was set on a job in the Northeast or the West Coast, and ended up in Oklahoma, but it's turned out to be a great place for me.
Be open to applying to different places. Maybe you're dead set against a 4-4 teaching job. That's fine, don't apply to them. It's good to know what you are and aren't willing to take. I'm just saying don't be too rigid about your goals or preferences, which may change in the future anyway.
The job market, particularly for tenure-track, is very random from year to year. With the same application, you might not get any tenure-track offers in one year, and get 5 in the next year. Most schools don't hire tenure-tracks every year, and the target area may change from year to year. This is also one reason some people apply for tenure-tracks before the final year of their postdoc. (I don't recommend applying every year though---the application process and the waiting is both mentally and emotionally exhausting, and makes you less productive. Plus, if a search committee sees your application 5 years in a row, they're not usually going to be much more excited to see it a 6th year.)
You may need to take a postdoc in an unidentified Scandanavian country before you get your dream job at the Harvard of Massachusetts. Maybe you have to do a second or third postdoc before you get a tenure-track position. Maybe you have to take a tenure-track position 48 time zones away from your spouse or favorite sushi place for a couple years before you can get a job in the same state (at which point the sushi place will close down, but hopefully your spouse will not). I'm not saying that these are the norm, but they happen.
If you want a job at a research university, it's almost a given that you need to do a postdoc first. It's not uncommon nowadays to do 2 or 3 postdocs (depending on the length), but if you're out for more than 6 years by the time you apply, your application needs to be pretty impressive. (Search committees will typically wonder why you haven't gotten a tenure-track position 10 years after your Ph.D.)
If you're not sure if you want to stay in academia or not, you could apply for postdocs in the fall and non-academic jobs in the spring. A postdoc might help you decide if you want to stay in academia, and you can still get non-academic jobs after a postdoc, but it's harder to get back into academia after leaving.
If you want to be unemployed (which, according to word on the street, is a pretty sweet gig now), that's great! You don't need to apply at all, so you can spend more time actually doing math!
I don't have the data on how many of these 900 US academic jobs were tenure-track versus postdocs, or how many of the tenure-track hirings were from foreign PhDs, so I can't give you a success rate of people immediately or eventually getting tenure-track positions, but it's not completely horrific.
In any case, if you want a good job (whatever that means to you), you need your application to stand out in some way. With the advent of mathjobs.org, we get hundreds and hundreds of applicants for each postdoc and tenure-track position, which means we can afford to be a little choosy. For a tenure-track position at my university, the first thing we look for is a strong research background in an area that fits in well with, and nicely complements, our current faculty interests. (This doesn't mean we don't want to hire in new areas, but there are certain areas we are unlikely to hire in. We're also unlikely to hire someone who does exactly the same thing 3 other people here already do.) Among these applicants, there are still far too many for a short list. At this point, we have discussions, and any little thing could cause some to be put on or off a short list. I'll talk about some things you can do to help get yourself on a short list, and maybe even get an offer.
Some things will evidently be easier at some departments than others, and I'm not suggesting you try to do all of these things---in fact I suggest you don't. Your primary duties as a grad student/postdoc are research and/or teaching, and you don't want to get involved in other activities at the expense of these.
You might not like to believe it in academia, but who you know (i.e., networking, as they call it in the big bad business world) can also make a big difference in where you can get a job. I got my job at Oklahoma partly because I randomly met one of the faculty here at a conference in Japan the semester I was applying. Before that, I got a postdoc with my advisor's advisor. Both who you know personally and who your advisor/postdoc mentor/letter writers know can help your application stand out. The reason networking makes a difference is not so much because we believe in nepotism or elitism, but mainly because it simply gives us more information (in terms of reference points) about certain candidates. (Though occasionally influential advisors may "pull some strings" to land a student a job.)
While there are some clear-cut cases, it's generally a pretty impossible feat to compare two mathematicians one knows well and say without question who is better, let alone thirty or forty that you only know on paper, especially when all the letter writers try to hype up each candidate. So if someone in your department can give first-hand validation of a candidate, or the candidate has a letter from a colleague you trust, this carries weight in the discussion of the candidates. (This may not be true for smaller departments or less research-oriented departments, or for postdoc applicants, but in our case probably half the applicants who make the tenure-track short list know at least one person in our department.)
This should be clear from the above, but, when you go to conferences, you should try to talk to different people. This may be hard at first, but after a couple conferences you should start seeing the same people over again and it should get easier to talk to them. I'm not saying you should introduce yourself to everyone because they might help you get a job later (networking for the sake of networking leaves a bad impression). I'm just saying don't be too shy. It may be easiest to start by hanging out with some of the other students/postdocs or people you already know, and eventually you should get introduced to more and more people. You should also feel free to introduce yourself to ask people questions (either about someone's talk or a specific research question you've had in mind for awhile).
Along the same lines, if you have a question for a specific professor but don't have a chance to see them in person, feel free to introduce yourself and ask them by email. (Make sure it's well thought out first.) But don't feel bad if you don't hear back for awhile. Professors often get bombarded with emails and may be slow in responding or miss occasional emails.
One conference that you should definitely plan on going to if you want a job at a liberal arts college is the AMS-MAA Joint Mathematics Meetings (JMM). These are the US math societies' annual national meetings in January (the location rotates). There's an Employment Center at the JMM where many smaller schools do preliminary interviews. Thus you should certainly go the year you apply, and register in the early Fall. You could even consider going the year before to see what the Employment Center is like, though I wouldn't make a long trip solely for this reason---just talk to someone who's been recently. If a school's interested in you, they may want to see you give a talk, so if possible you should try to arrange to give a talk in one of the sessions. (You might also need to give a talk to get funding from your university.) You can either just request to give a "contributed talk" when you register online in advance (check the deadlines by the summer) or try to arrange to give a talk in one of the special sessions. Special Session slots are typically more desirable but fill up fast, so if there's an appropriate special session for you to speak in, try to contact the organizers for that session in the early summer beforehand. (I think list of special sessions is usually released around May/June.)
Here are some things that should be on your webpage.
First you should list your papers and your thesis, with links, if you have any. It's become common now for job applicants to list titles of papers in progress with the words "in progress" or "in preparation" next to them. These should be things where you already have substantial results. Whether you do this or not is largely a matter of taste, but I personally prefer to wait until something is done to list it (it may never materialize---the best laid schemes o' mice an' men---and then people may start to wonder). When looking at job candidates, if I see "preprint" without a link or something "in preparation", I attach little weight to this, in part because some people use these words rather liberally. The only real benefit is that it helps me quickly form an impression of your current research topics. (Note: before you list or post anything that's a joint paper, clear this with your collaborators first.)
It's also good to make a brief bio. For example, "I'm a third-year Ph.D. student under Professor Quincy Magoo at Ewe U studying topological modular forms and forgetful functors." Even if you don't have any papers yet, you can still make a webpage with this sort of information. However, if you say what year you're in, try to keep this information up to date. If you have a picture of yourself that came out better than your driver's license photo, it's not a bad idea to include that either. That can help people match your name with your face at conferences. Plus, just having a face to your name can make you stand out a little more in the mind of someone you haven't met.
You can also list what classes you're teaching/TAing for. If you make any teaching materials for students, you can link it from your homepage. Also, it's often helpful to type up notes for material you're learning and you may want to post some of these. These notes might be useful for someone, and may make you a little more well known. (I find many students on Google this way.)
Other bits and bobs: You might include links to pages you visit often. Some people list conferences they've been to or will go to. Some people post their CVs. Some people include things about non-mathematical interests/hobbies as well. Try looking at some other mathematicians' webpages for other ideas.
Other online things you can do are particpate in sites like MathOverflow and MathStackExchange. These are forums where you can ask math questions (including career advice) and give answers. It's a good way of finding out some things that aren't easy to find in the literature and seeing what else is going on in the world of math around you. I recommend making a profile with your real name and info, and put a link to your webpage. Often I'll try to check out who a certain poster is if they post something I find interesting. Just make sure your posts are properly thought through before you submit them, and try to make sure your questions aren't duplicates (this annoys a lot of users). You can also get into mathematical blogging if you're into writing (or mathematical tweeting/instagramming if you're not into writing), though it takes a fair amount of effort to blog a good blog.
First, longer postdocs are better. The more years you can go without applying for jobs, the more productive you'll be. Often all you get done during the first year your first postdoc is improving, rewriting and submitting your thesis and getting acclimated to your new life as a postdoc. (You should avoid this, of course, but easier said than done.) If you have 2-year postdoc, you'll need to apply in the fall of your second year, so by this point all you might not have done anything more than your thesis. This is not ideal. A 1-year postdoc is even worse. If there's a short postdoc/special program you want to go to, you can often defer another postdoc for a semester or a year, and line up 2 postdocs without having to apply twice. This is good (though the extra move may hamper productivity some).
Second, more prestigious postdocs are better (at least for research jobs---if you want a liberal arts job, it can be an advantage to do a postdoc in a liberal arts enviroment). All other things being equal, would you rather hire someone who did their postdoc at Stanford or at Unremarkable Name University? That's what I thought. (The same goes for your PhD institution, but by the time you're reading this, it's probably too late to change that.) Besides that, being at a school with a higher level of research (at least in your field) will help make your research better---you'll meet lots of experts and learn many more things.
Third, when possible, choose a postdoc with people you can work with, or at least discuss research with. Many times I've seen postdocs go somewhere, be isolated, and have their research stagnate. (It can also happen that you go somewhere hoping to work with Professor X, but you don't end up talking much at all. You can try seeing how Professor X's previous postdocs fared, and whether they did any joint projects together, though past performance is no indication of future results.) You may be independent by the time you're a postdoc, or you may still need guidance. Either way, having someone to mentor you at least in some fashion is a big plus. Often a (formal or informal) postdoc mentor may play as large a role in helping shape your mathematical career as your advisor has, so choose wisely!
Fourth, try to land your last postdoc in the US. Maybe you want to go work with someone in Europe, or race with kangaroos down under. That's fine. However, when you apply for tenure-track jobs, it's best to apply from the US, or maybe Canada or Mexico, if possible. This doesn't make a big difference for all schools, but many schools with a limited budget won't want to pay to fly in someone to interview from outside the US. (Though a few schools may be willing to do Skype interviews.) In addition, many places will want to see that you have teaching experience in the US system. So if you want to do a postdoc abroad, plan on doing another one in the US afterwards (or at least apply as a backup option).
Note: for teaching-only jobs, your specific research area is not so important. The only relevant thing is that you should be clearly well qualified to teach the classes they'll want you to teach.
The standard places to look for US job openings are mathjobs, EIMS, and The Chronicle for Higher Education. Most research jobs will advertise on mathjobs and/or the EIMS. Some places will advertise late, so you should periodically check for new job postings.
The most important things for your application will be the letters of recommendation, your publication record (for research jobs) and your teaching experiences (for teaching jobs).
A question people often ask is: "Should I customize my cover letters to individual schools, or is a generic cover letter okay?" My feeling is many liberal arts schools want personalized cover letters and most research universities don't care, though of course it depends on who is reading your application.
The main reason to customize your letter for research schools is just to make sure the right people read your application. (In the past, cover letters were often read by secretaries and based on this referred to appropriate faculty to review. Now, with online applications, this is not a big deal as all faculty members can look at whatever files they want, but it may still help keep your application from getting overlooked.) So if there is someone at the school who you think will be seriously interested in your research (don't stretch this, which can make your application look desperate), then you can either mention them in your cover letter, or just send them an email after you apply pointing out your application---you can even attach your application materials in the email if you like. (Again, don't be offended if you don't get a reply. We often get lots of these emails.)
The main reason to customize your letter for liberal arts schools is to convince them why, out of 200 billion liberal arts schools in the galaxy, do you really want to teach at Oompa Loompa College? (location? faculty? the rhyming acumen of the students?) Since many liberal arts colleges read cover letters first, you also want them to get excited about you in the cover letter. Show how you're different from other candidates (but not in a bad way), so they'll pay extra attention to the rest of your application.
You can find many examples of CV's online, but the basic information it should have is your name/contact information, educational history (bachelor's to PhD, with advisor and thesis title), professional history (e.g., postdocs, graduate TA positions, summer programs), your publications/preprints and your teaching experience. Also, a cell number can be useful if a school decides they want to set up a second interview with you at the JMM. It's also common to include things like invited talks, awards, conferences attended, service activities (journal refereeing, conference/seminar organizing, MathSciNet reviewer, etc) and computer skills (programming, mathematical software). However if you've only given one invited talk, or only been to one conference, I wouldn't advertise this. Some people also include references, but again, as this is in the Cover Sheet, it seems unnecessary to me.
This isn't crucial, but you might even consider a making a "Research CV" for research jobs with all your research information up front first, then teaching experience at the end, and a "Teaching CV" for teaching jobs, with your teaching experience up front (or at least before talks, etc). Remember that whoever's reviewing at your application is probably looking at hundreds and hundreds of others as well, and might not spend much time on yours unless you show them what they want up front.
The format is not so important (chronologically, backwards or forwards, is standard). Just provide complete citation information for all published papers. For papers which have been officially accepted, but have not yet appeared in print or electronically, say something like "Pointed Journal of Pointless Topology, to appear." For papers which have been submitted, but not yet accepted, just say "submitted." Some applicants might say "Submitted to Annals of Math," but where you submit doesn't mean much unless it's accepted. (If it really should appear in the Annals, then at least one of your letter writers should say something to this affect, and that will mean quite a bit.) If you really want, you can say where you submitted it, but I don't recommend it in general.
However, if you have a paper that has been favorably refereed, and the editor asks for a revision but hasn't officially accepted it yet, some people write something like "under revision for Pretentio Mathematica." (Occasionally I see "accepted pending revision" but you should only say this if the journal tells you this.) Provided the journal is good, I think this is okay to do, as this means the paper will most likely be accepted there, though it doesn't mean as much as "to appear."
For papers you're working on, but have not yet submitted, you can either list them as "in preparation" (I take this to mean you have some results, possibly complete or not, but you haven't written up anything nice enough to show people) or "preprint" (this should mean you have your results, and have it written up, but maybe are still revising it), or not list them at all. The choice is yours, as discussed with your webpage. If the preprint is disseminated (e.g., on your webpage or on the arXiv), but for whatever reason not submitted yet, then you should list it as a "preprint" with a URL (this makes it clear the preprint is "done").
As to what the search committee will want to see on your publication list, this depends on both the school and the field. There are a few schools that may just count your number of publications and not how good or involved the papers are. However, I think most schools take into account the quality of your publications as well as what is typical for your field (often it's 1-2 per year, but for some fields 4-5 per year is normal). Consequently, there's no set minimum for the number of publications you need. As a general rule of thumb, I expect applicants for research jobs to have roughly at least 1 publication from their thesis and 1 for each year they've been out since (though less is okay if your papers are outstanding). So if you do a 3-year postdoc, and apply for a tenure-track position in your 3rd year, this means I'll typically want to see at least 3 papers on your publication list: one from your thesis, and two publications/preprints for your first 2 years of postdoc. At least 1 or 2 of these should be accepted now. (Note: update your mathjobs application when a paper gets submitted or accepted.)
The reason it's important that papers be accepted (by good journals) is that this is one of the very few pieces of external evidence of your "research quality." (And this again becomes important at the tenure stage.) Consequently, the better the journal (e.g., in terms of impact factor or reputation) you can publish in, the better your research will look on paper. At research universities, we look for some ill-defined combination of quality and quantity. We don't typically want someone who's been out for 6 years and has only published 1 paper even if it's an Annals paper, or someone who publishes 10 papers a year in the Journal of Unpublishable Mathematics. (However, the latter is certainly worse, and this is coming from an editor.)
Now comes the hard part, which you should be reading way in advance. To compile a compelling publication list you need to do a couple of things. First, you need work on suitable problems (i.e., avoid ratholes and 10-year masterpieces). While it's important to spend a fair amount of time thinking about what are good questions to ask, you can't spend too much time doing "open-ended research" at this stage, or you'll never have any publications.
Second, be quick about writing up and submitting what you do have (in particular, submit your thesis to a journal by the first semester of your first postdoc---preferably before). Remember that only what is done by the early Fall of the year you apply will help you in your job application (including what your letter writers write). Many young people spend too much time trying to make their results just a little better, only to find a year has gone by without accomplishing anything of note. It's okay to not solve a problem completely and still publish what you have (as long as it can get into a reasonable journal). If you figure out how to do more later, you can publish that later, and now you have 2 papers!
Of course, at what point you should publish your work is a fine line, and if possible you should get some advice from someone in your field (do they think what you've done so far is worth publishing yet or not? if so, don't wait!). My rule of thumb is after I have something worth publishing, I give myself 2 weeks to think about whether I can improve my results. If, within these 2 weeks, I have a semi-coherent plan for how to do this that seems feasible, then I'll give myself a certain amount of time (e.g., a month) to try this. If it works, great, I've improved my paper without too much delay (though in practice that 1 month I've given myself turns into 2-3). If not, then I'll submit what I have and maybe work on this improvement later.
I want to emphasize that writing up your results quickly does not mean that you should be sloppy about it. You should take your time and be meticulous. (The actual writing and revising may take weeks, and at some point you may discover you just need to scrap everything you've done and rewrite from the beginning in a different way.) In particular, the introduction should clearly explain the background, context and significance of your work. Often the process of writing a good introduction will give you better insight into the problem, and may suggest additional results or future projects. Furthermore, how well you "sell" your results in your intro can make a big difference in getting your paper accepted. If your paper is not well written, that means it will take more time for the referee to read it, and lower the chances of acceptance. For more advice, see Terry Tao's advice on writing papers. There's also Steven Krantz's article, How to write your first paper, though I don't agree with everything in there.
A word of caution: with collaborations, you don't have complete (or sometimes any!) control over when you can get a paper submitted. Some coauthors are notoriously slow and/or picky about writing up results. Just make it politely clear to your coauthors that you'd like to submit as soon as possible since you'd like to have this submitted/accepted/published by the time you apply for jobs, and do your part quickly.
Third, when you submit your papers, you have to choose an appropriate journal, preferably one that is reasonably quick about acceptance, and one that you have a reasonable chance with. (The AMS publishes data on journals' average backlogs and processing times.) The downside is that both the timing and the decision are highly dependent on the referee, who may be very quick or very slow, and may or may not be able to properly understand your revolutionary opus. After 6 months to a year, it's acceptable to send an inquiry to the editor about the status of your paper, which may help speed things up. (It can't hurt to politely mention that you'd appreciate anything that could be done to expedite the process since you'll be applying for jobs in the near future, though there may be little the editor can do.)
You'll have to balance your odds of your paper getting accepted together with the reputation of the journal. Some people take the approach of figuring out what journal is appropriate, and then trying "one level higher" just in case they get lucky. This may be okay if you have many other publications, or aren't in a hurry, but at this stage I recommend against betting on a longshot. If you need the paper to be accepted within the next year, choose a journal that's fast, reputable and is likely accept your paper. Of course, it may be difficult to choose a journal of the appropriate level, but hopefully an advisor or colleague can give you some advice. Also looking at impact factor rankings, browsing recent issues, and checking number of articles published per year can help give you some sense of your chances with different journals.
Well, good luck with that.
In all honesty, I don't read most candidates' research statments too carefully. Normally I look at the CV and letters of recommendation, and then if the application seems interesting, I'll look at the research statement to get more details. However, when I get to this, I want this to be easy to read, and I want to see that the applicant can both clearly explain what they are doing and how it fits in the context of the existing literature.
Therefore, I suggest beginning by writing a gentle introduction readable by someone not in your field (if you're an analytic number theorist, I don't mean make it understandable to an algebraic number theorist, I mean make it understandable to topologists and combinatorialists). Then you should write about specific work you have done, including appropriate background, and give a brief summary of the method of proof and how your proof is different than or similar to arguments in previous work. Here I think it is better to focus on making this as understandable as possible to people in different fields (or at the least, people in your general area), rather than making sure you state every condition and defnition precisely, or state everything in full generality. (People who are really interested will look at your papers.)
At the end (either at the end of your statement, or at the end of each project discussion), you should discuss possibilities for future work and talk about your future (short-term and/or long-term) research goals. However, you don't need to go into a lot of detail---this is not a grant proposal. The main goal of your research statement is to explain what you've already done and its significance, and convince people you'll continue to do interesting work. If you've done things like supervising undergraduate research, this can also be mentioned here, or possibly in your teaching statement, depending on which you feel is more appropriate. If there are some related questions that would make for good undergraduate research projects, say this in your research statement, particularly for schools without graduate programs.
If you're applying for both research and teaching jobs, you should write two separate research statements for these two kinds of jobs. For liberal arts/teaching schools, you should be more introductory and put an extra effort in to making it readable, as chances are there will be no one in your field at these schools. In both cases, you want to make it clear that you have a solid research program with a lot of momentum, so that you will still be able to continue your research with all your newfound professorial duties. (For teaching-only positions, you probably won't be asked for a research statement.)
As for length, I would generally recommend 4-6 pages for a tenure-track research job, and at most 3-4 pages for a job a liberal arts school that expects some research (or a first postdoc). If it's too long, people are discouraged from reading it. Similarly, if the font is too small, or it looks too "dense," people are discouraged from reading it, so try to write it in a relaxed, friendly style in, say, a 12-point font with (at least) 1- to 1.5-inch margins. Where feasible, state Theorems, Problems, Conjectures, etc clearly, so someone skimming the research statement can quickly find the main points.
One approach to writing research statements (as well as grant applications), is just to write a summary of your research in a fair amount of detail without worrying about length. Then after realizing it is way too long and/or technical, you can go through and try to simplify it. This can also be useful as it gives you an "extended research statement," which you can distribute to your letter writers and/or email to experts at places where you're applying. (Personally, I often find that---as with introductions to papers---after writing a first draft which is too long or technical, the best thing is to start over completely for a second draft. It often makes your writing much clearer than trying to carefully edit and re-edit, and sometimes ends up being faster than wrestling with consistency fixes on edits and re-edits anyway.)
The best teaching statements I've seen were not just compiliations of some general philosophy about teaching (though they may include that), but were filled with detailed examples of things they do while teaching or stories of how their own experiences as a student shaped their teaching philosophy. (This is similar to the writer's rule show, don't tell, except here maybe you should show and tell.) Maybe you hold office hours at 5am every morning at IHOP to accomodate all those early-riser students; maybe instead of writing your lecture on the blackboard you tweet it in l33tsp34k to connect with the younger generation; maybe you post videos online of your students crying after exams with the caption "d0nt l3t th1s BU!" to motivate them to study. Discuss your brilliant teaching innovations and, if possible, provide evidence for how helpful they were (e.g., you had record-setting participation in your early morning office hours, or your student evaluations/restraining orders contain compliments like "1m gl4d 1 f1n4lly m3t 4 t34ch3r wh0 4cc0m0d4t3s m`1 m3d1c4l c0nd1t10n 0f b31ng \/n4bl3 t0 r34d v0w3ls" and "If the US were to send a teaching delegation to North Korea, I nominate Dr. Martin for the first to go"). Your teaching letters should include some student feedback, but if possible, you should incorporate it into your teaching statement as well.
A corollary to this is: to make a good teaching statement and Supersize your teaching resume, look for interesting ways to spice up your teaching, and try new things to continue improving. It's often hard to think of specific examples and recall details when you need them, so it might be a good idea to periodically write in a "teaching diary" about your teaching experiences, which I think will also help shape your teaching philosophy and let you write a much better teaching statement when the time comes. (This could even be part of a math blog you write, and if you blog, you might get some useful feedback/suggestions.)
This said, the teaching statement itself tends to make little difference for a research job. (This doesn't mean it's okay to do a crappy job---some people will still look at it, and if one part of your application looks bad, that's one strike against you. And if you manage to craft a truly insightful teaching statement, people will be more easily convinced you're a deep thinker.) For a teaching job, it is probably more important. Read the job ad carefully to see if there is anything specific you should address in your teaching statement (e.g., philosophy on use of technology in the classroom).
For length, I'd say between one and a half to two pages is normal (using the same format as suggested for your research statement).
First, you should typically ask people for letters at least a month before your first deadline, though maybe a month and a half is a little better (more for teaching letters, see below). When you ask, let them know the earliest deadline you have. Once they (hopefully) agree to write you a letter, you should send them an updated CV and your research and teaching statements (you can send an extended research statement with more details). Give them a link to your webpage from which all of your papers should be downloadable. (With co-author permission, you may also want to send them copies of preprints not yet disseminated.) This means you need to finish your preprints and a draft of your application by September.
It's important to tell your letter writers what kinds of jobs you'll be applying for, as most letter writers will try to cater their letter for your situation. (They'll typically only write one letter, but if there are specific things you want them to address (read some job ads first), then let them know.) Of course you also need to tell them how to submit their letters: the mathjobs ones are straightforward---for other applications, give them the submission and deadline information in an easy-to-read format, and offer to provide stamped pre-addressed envelopes for any mail-in applications, if such things still exist. Feel free to send a friendly reminder a week or two before the deadline(s), and then another one a few days after the deadline if necessary. (You can see when letters are uploaded on mathjobs. Don't worry if all your letters don't arrive by the deadline---it's usually fine if 1 or 2 of the letters are a little late.)
For research universities, get at least 3 or 4 research letters and 1 teaching letter. Four (4) research letters is probably typical for tenure-track research positions. It's okay to submit more letters than are asked for, but it's not okay to submit less---what's listed are minimum requirements for the application. However, I don't usually want to see more than 6 letters in total, and there's typically no reason to submit more than 1 teaching letter for a research job.
For liberal arts colleges, often 3 letters are required, but you might want to aim for 4-5. Read the job description to see what they're looking for: maybe 2 teaching letters + 2 research letters is appropriate; maybe 4 teaching letters + 0-1 research letters is better. (On mathjobs you can customize your Cover Sheet for different schools, so different schools get different combinations of letters of recommendation.)
Let me talk about the research letters first. In normal circumstances, your thesis advisor should write one of these letters. For research tenure-track jobs, it's good if you have letters from people from different institutions, preferably from well-known experts in your field. You should not just select letter writers on the basis of who you feel the most comfortable with personally. You should ask people who are familiar with your work (you need not have met all of them in person even), understand it's importance/context, and have a good opinion of your work. (You may not think your work is important, or have any idea what someone's opinion is, but your work is probably interesting to someone. Just make mental notes when someone asks you questions about your work, invites you to give a talk, makes comments after a talk, etc. These are indicators that that person has some interest in your work, and people are generally kind when they write recommendation letters). It can also be good to have a (research or teaching) letter from at least one person from each institution you've been at for a significant period of time who can discuss what kind of colleague you are/were and how you contributed to the department, but, at least for research jobs, this is a secondary concern.
I want to emphasize that these letter writers should really be experts in the field, not just someone in a related field you know that has seen you give one or more talks. Recommenders will only write in detail about what intersects their area of expertise, so if you work in a couple of different areas, you should try to get letters from both areas. It can happen that you have a great paper but none of the letter writers discuss it in detail because it's not their field and they expect someone else to. (You might inform your letter writers who your other letter writers are, which is sometimes useful in guiding the letter writer what to talk about.) Furthermore, the closer your letter writer is to your area the more enthusiastic they will typically be about your work. In addition, the more senior/well-known the person is, the more weight their letter will carry. (Exception: if you're just looking for teaching jobs, then it's probably more important to get letters from people who know you well and can comment on how you will be as a teacher and a colleague than to get letters from high-profile researchers.)
Senior faculty often write letters for several candidates in a given year (and we often compare these letters from the same writer to compare the candidates), so you need to make sure the people you ask know (at least part of) your work well, or their letters will be less enthusiastic. This is one reason why it's important to go to conferences and give talks. For letter writers at your institution, or at least ones you can easily meet, you should offer to meet with them to explain your research one-on-one.
Note most research letter writers will include a little bit of what they think of you as a teacher (this could range from a sentence to a couple paragraphs), e.g., your advisor may comment on how great a TA you were as a grad student, or someone will say you gave a conference talk with amazing clarity, and hence they think you'll make a great teacher. The former can be quite informative, but the latter is worth its weight in lead for teaching schools. So if you're focusing on liberal arts/teaching jobs, then it may be nice to find a letter writer who can address both your research and teaching in some detail, if there is someone appropriate (and let them know this is what you want).
If you're still not sure who to ask, try asking your advisor or another colleague for some suggestions.
Now let's move on to the teaching letter(s). Generally you should get a letter from someone at your current institution. There's a good chance that your department has a standard person to write teaching letters, and unless there's a specific reason not to (e.g., that person's writing already you a research letter or someone else is more informed on your teaching), you should probably ask them. Some of these people are very good at writing teaching letters and some are very bad. (After seeing other letters written by my teaching reference, I have no idea how I got any liberal arts college interviews at all---it must have been because of my extracurricular work with high school students and undergrads.) Try to ask someone who is senior (definitely NOT your postdoc friends), cares about teaching, and cares about you getting a job. If you've done a significant amount of teaching at another institution, consider getting a letter from someone from there also.
You should make sure your teaching letter writers have access to your past student evaluations and know what kinds of jobs you'll be applying for. For primarily teaching jobs, it's important that at least one of your letter writers has observed you teaching. (Otherwise the letters are forced to be pretty generic.) Thus you should invite your letter writer(s) to sit in on one of your lectures (make it one of your better ones). It may take time to coordinate this, and this person may have some suggestions and want to schedule a follow-up visit. Thus you might want to pop the "will you write a letter" question a couple of months in advance. You might also ask for feedback on your teaching statement (hopefully, this will encourage your letter writer to at least read it, after which they may be able to write you a better letter).
Note to non-native speakers: Many schools would like you to be able to communicate effectively and easily in English, mainly so they don't need to worry about students complaining that they can't understand you. Both your advisor and teaching letter writer(s) will probably address this point. To make sure they can say something good, you should actively try to improve your English if you are not fluent (e.g., take classes or get a conversation partner), particularly if you repeatedly see complaints on student evaluations. Even if you're not fluent, if your letter writers notice that you are trying and making progress in improving your English, it will be looked on favorably.
At the JMM, there used to be two kinds of interviews: the Math Meat Market (pre-arranged interviews), and the Mass Math Meat Market (5-minute interviews arranged on site, if I recall). Due to unpopular demand, I am happy to see the Mass Math Meat Market has been discontinued. This is a boon for everyone involved. If you get a JMM interview, read their advice.
For both the JMM and phone/Skype interviews, remember the interview will be short (typically not more than 30 or 45 minutes), so it's important to prepare to get across what you want in this limited amount of time. First, you should research the school/department and be able to give clear and compelling answers to basic questions without much delay: e.g., why are you interested in this school? how would you fit in with our department? what is your research? what is your teaching experience? what are your best/worst teaching experiences? what innovative things have you tried in teaching? what are your long-term career goals? what classes would you like to teach/can you teach? how do your research and teaching fit together? what does a liberal arts education mean to you? do you have any experience teaching in a liberal arts setting? working with undergraduates on research projects? using technology in the classroom? what are the most important classes for a math major to take? if you could design class XXX from the ground up, what would it cover? what do you to do motivate students who are uninterested?
The questions of course will vary from school to school, and person to person, and there will probably be some questions you won't anticipate, but that's okay. (Your first interview will be a learning experience.) Even if you don't have a good "direct" answer, you can try to still give a good "indirect" answer: I haven't directed any undergraduate research, but I worked on a research project when I was an undergrad and it made a big impression on me, and I'd like provide other students with the same opportunity, or No, but there's this problem (explain in 10 seconds) that came out of my research that I think would make a good undergraduate research project..., or I haven't taught in a liberal arts setting, but I really look forward to doing so---[insert specific example about working closely with individual students, or getting students to learn how to think through something for themselves, and say how satisfying it was]. These kind of answers sound much better than a curt "No," though you probably don't want make yourself a politician by giving all indirect answers.
Some other general advice on answering questions: Remember the interviewers have been in your shoes before (not literally, but something close). All the interviews I've had were quite friendly, so try to be relaxed and know that they expect (not in the hopeful sense, I hope) you to be a little nervous. If you don't understand what they're looking for, try asking for clarification. Try to answer all questions sincerely and enthusiastically (don't give rote answers). When possible and appropriate, as with the teaching statement, try to give answers with specific examples or little stories or ancedotes. This will help your answers stand out more in the committee's mind, as well as make the committee feel like they know you better. Lastly, if you know someone at a similar kind of school, or someone who's done a similar kind of interview, try asking them for tips and what kinds of questions they were asked. If you have a good friend or mentor who's willing to do a mock interview with you, that's even better.
The other part of your JMM/phone/Skype interview will consist of questions from you. You should have some prepared in advance. This provides an opportunity for you to get some sense of what the job would be like (which may elevate or lessen your enthusiasm for the job), but your questions also give the interviewers some sense of how interested you are in the position (hence having no questions is bad). Some typical things to ask about are: teaching expectations (how much and what), research expectations, opportunities for working with undergrads, service/administrative expectations and questions about the school/town. Information the interview committee brings up about their department may also prompt to to ask further questions about the plans of the department (maybe they're trying to start an undergraduate research program, are revamping their major, or planning several hirings). Don't ask about salary or benefits yet---it's premature (wait for an offer). Personally I would wait for an on-campus interview to ask about details on the tenure/promotion process, though it's fine to ask about what is the normal tenure clock is and if one can count postdoc experience against this. If you have a two-body problem, you might want to bring that up now (more on this later). Remember, there probably won't be a lot of time for your questions, so ask the important ones first, and the others at the on-campus interview.
Okay, let's move onto the on-campus interviews. These typically happen in early Spring (though recently some schools have been starting in December) so if you can arrange your teaching schedule in advance to teach less in the Spring Semester/Winter Quarter when you'll hopefully be interviewing, it will make travelling a little easier. At least consider trying to get at travel-friendly schedule---you don't want to have to catch a late flight because you have to teach and only get 3 hours of sleep the night before you interview. (Remember this is also the season of weather delays, so avoid flights through Chicago.)
For your interview, you should have a host who will help coordinate your visit. Generally, the host will be "on your side," so feel free to ask them any questions you have. When you arrange the interview, you might see if it is possible to stay an extra day or two to get a better feel for the department/school/vicinity (the department will reimburse you for your trip, and often this is no problem, but if their budget's tight it might be difficult---occasionally, schools may be willing to pay for a spouse/partner to come also, but this is quite rare). As with the JMM/phone interviews, it's a good idea to do some research on the department/school/vicinity before you go, so you can ask intelligent questions and prepare your talk(s) appropriately.
The interviews can be quite different at research schools and liberal arts colleges. At a research university, the dress is casual (I'm a bit turned off when candidates show up in a suit, not that I want to see you turn up in a dirty T-shirt---smell is still important!), whereas for a teaching school (on-campus or at the JMM, and maybe also for Skype interviews), you should dress up (men: a tie is safe, a suit is fine but not necessary). Most of the time at the interview just consists of meeting people, letting them tell you about the school/department, and having a chance to ask each other questions. There's no reason to get worked up about this "meet-and-greet" time, it's usually casual and friendly. Just be sincere and respectful, show genuine interest (if you don't have any, this isn't the job for you), and don't try to oversell yourself.
On the other hand, there are serious parts ("go time") you definitely need to prepare well for. For a research university, it is typically just your "job talk" (a research talk aimed at the whole department). For liberal arts/teachings job there usually are two components: job talk(s) and interview(s) with faculty. The job talk(s) will consist one or two of the following: a research talk to the faculty, a math club type talk to the undergrads, or give a lecture in a classroom setting. When you set up your interview, it should be made clear what kind of presentations you are expected to give. The interview with faculty is basically an in-depth version of the JMM/phone interviews we discussed, and the same advice applies here. So I won't discuss this further, except to say, here (and possibly at a phone/Skype interview) there will likely be non-math/science faculty asking you some questions (possibly including a dean or some higher-up), so you should be prepared to explain some of your research/teaching to a "lay audience." (You can ask who will be at the interview in advance.)
At both kinds of interviews, there should also be some official time for you to ask the chair and/or faculty and/or students some questions, so as with the phone interviews, you should think about what questions you have in advance, but you'll probably be free to ask whatever questions you have throughout your visit. And you may want to ask the same questions to different people to get different opinions.
What about the content? For a research job talk to faculty, you should try to make at least the first 30-45 minutes basically accessible to everyone (assuming the talk is 60 minutes---the length should also be made clear to you in advance). In other words, even if they can't follow all the details, they should understand the main ideas. This is one reason why it's important to practice and get feedback from someone not in your research area---it's hard to gauge what other people not in field your will know/be able to follow quickly. I can't give you very specific advice as to how to organize your talk, as the best way to give your talk will depend on what area you work on and what you actually did. It may be best for you to start at the origins of the problem and build everything up slowly like a nice survey talk until you get to your results and then discuss a proof, or maybe you should give a 5-10 minute overview before going into things in detail. Maybe you have one main result or a sequence of related results. Maybe you will need to introduce a lot of background and briefly sketch a proof in the last 5 minutes, or maybe little background is necessary and you can spend 30 minutes on proofs. Maybe a board talk is better, or maybe a computer talk is.
Here are some points to keep in mind for the research job talk, though some of these points are more-or-less applicable to other kinds of talks. It's good to start with a clear, brief historical motivation for your work that a beginning grad student or even undergraduate could appreciate. Try not to wait too long before stating (at least vaguely) what your results are. Don't expect people to have read your research statement (or any of your application) before the talk. Don't be an ass. Be clear about contrasting how your result compares with previous work, and why it is interesting/useful. Try to give some indication of your proof/solution, highlighting how it is different from previous approaches. Try to indicate future possiblities of your approach. If forced to choose, I would spend more time putting my results in context than on elaborating the proof. Be precise as much as possible, but not too technical. You want people to be excited after your talk, not exhausted. Don't go over time. Make sure you can say what you want to in the time allotted, allowing for several questions from the audience (your timing should be hammered out in practice runs). If you realize you can't finish on time, figure out how to shorten it on the fly. Anticipate questions that the audience may ask, and try and make sure you can answer them (can you define everything? state the theorems you use? say the main point in the proof of a related result?), but be willing to say "I don't know" when you don't. Know your talk well enough that you can give it essentially without referring to any notes. Know your audience. E.g., if you're an analyst, and the department is full of geometers and topologists, see if you can emphasize some geometry/topology. This may make some people outside your field get excited about you.
See also some thoughts from Terry Tao and others (through the links below) on giving talks in general.
The next kind of job talk is a talk to undergrads (expect the faculty there as well---in fact the faculty might outnumber the undergrads). Here you may be asked to give something like a "Math Club" talk to students who know nothing more than single-variable calculus. (Make sure to clarify exactly who your audience is, what they know, the length of the talk and any other directions.) Often it's not expected that this talk is about your research, but if you can touch on your research in this talk, that's a plus. Here what the faculty are probably looking for is some mix of your ability to teach a semi-advanced topic and get an idea of your field of research. For example, when I did this kind of job talk, I gave a talk about the very elementary problem of representing numbers in the form x^2 + ny^2 and the work of Gauss. This allowed me to discuss Dirichlet's class number formula and say that one of my recent research projects was to prove a "higher-dimensional analogue" of this, though I didn't say any more about my research than that. Note the faculty may solicit student feedback on you, so pitch it to the students. Perhaps you can do a practice run in your local math club beforehand. (If you're not sure what to talk about, you can suggest a couple of topics and ask your faculty contact their opinion.)
As for the "classroom job talks," I've never done one (thank God!), but what I hear is that you may be asked to substitute teach for a day, e.g., give a lesson on Section X.Y out of Euclid's Elements (and again expect faculty there). Here also, the faculty may get student feedback on your performance, so prepare well, and if necessary clarify what the students will have seen before and what exactly you should cover.
At least by the time of your first interview/shortlist (and certainly by the time you get an offer), you should seriously consider disclosing your 2-body problem. Usually the department will try to help in whatever way it can. And if you're willing to take the job without an immediate solution to your 2-body problem, you should be clear about this also.
Once you have an offer, you should try to negotiate. Often the salary is negotiable, sometimes startup funds are, and sometimes temporary course reductions are. If they offer you a 6-7 year tenure clock, you can often a negotiate a shorter tenure clock in light of years you've spent postdoc-ing. For research schools, sometimes you can also negotiate leave in your first or second year if there's a special program you want to go to. You can negotiate a little even without any other offers, but you'll do much better if you have a second (comparable or better) offer in hand. Your department contact (probably the chair) is usually on your side in this process so feel free to openly discuss the negotiation. Remember that your salary increases will typically be percentages, so even a little salary negotiation now can make considerable difference in the long run.
Good luck. Bye bye.