Wren asked me to discuss this, so I'll do that now. If relevant, I can write the sequel later. As mentioned previously, I don't plan on turning this into a trilogy.
It should be mentioned first that this stuff works differently in math than in other subjects---first, nearly all math postdocs teach and nearly all math postdocs are hired through a department (or an umbrella group that's between departments), although some research groups have their own postdocs and of course people can get NSF postdocs and other similar things. (In most cases, though, some faculty member does usually have to be willing to serve as some sort of mentor so it's not like you can come out of left field---the difference is that it is
extremely rare for the money to come out of their pocket.)
One effect of all this business is that math postdoc hiring seems more seasonal than other fields. I've heard of plenty of physics postdocs, for example, who may start at any point in the year, but math postdocs are almost always synchronized with the school year and the timing of the job advertisements reflect this.
If you are planning on starting a postdoc, say, in fall 06, you should already have contacted your recommenders and prepared your package. Your CV should be easy to read. In math and physics, it's fine to be long (and expected to be comprehensive) but don't put more important stuff at the top because attention spans decrease exponentially. Your research statement should also be polished. They don't usually help you but you if it sucks, they
do hurt you, so you have to take it seriously. (I'm going to forgo talking about this more, because I think the culture of such statements varies widely in different fields.) For math, some schools will also want teaching statements. For your publications, under review is
not a "publication". That annoys many of the people reading your application, and you don't want to risk that. "Under review" is a separate category. "References furnished upon request" is also considered obnoxious by many people. Either list your references or don't.
Finding where to apply: If your advisor is well-connected, he/she may hook you up. This helps a lot, but I was on my own, so here's what I did. The official magazine publications of your field typically have loads of job listings around the right time. In my case, this means SIAM News, Physics Today, and The Notices of the AMS (and the AMS, in fact, has an extensive online database that is absolutely the best listing for any sort of mathematics). Other societies have similar things both online and in print, so go to the website of your relevant online organization and see what their resources are.
Make life as easy as possible for your recommenders. Give them mailing labels. (I have good latex code for this.) Give them plenty of time before the deadlines. Give them a list of everywhere that you're apply with the deadlines in easy places to find. (I know a bunch of the stuff I mention is generic, but it's better to go through it anyway.)
Now, I did contact a couple professors to apply to them directly. If you are going to see them at a conference, let them know you'll be there and ask if they have time to meet. If that's not possible, name-drop your advisor if your advisor is somebody they'd know. Drop some other connection if possible. (You know, if they went to Caltech, I have used that one very successfully in getting people to answer my e-mail. The idea is to bring up things you have in common so that they know you're not some random schmuck who is applying for a job because you found their name via a google search. Professors get tons of e-mails like that all the time, so the e-mail needs to show that you actually looked at their stuff.)
Attend lots of conferences (throughout your
entire graduate school career!): This actually starts much earlier than when you're applying for jobs. This is
especially good if you are going to contact an individual. Give not only short talks but also posters. Posters are your big chance to talk to profs one-on-one. At the applied math conferences I attend, many of the big-shots do go to the poster sessions (which are conveniently combined with the dessert sessions). This is the big chance to drop off some reprints, discuss your work, and impress people. (You can also blow it too, of course, but if you're going into academia, you need to meet these people. Match the faces to the names you see in the journal articles.) Arguably, my first postdoc was a direct product [as opposed to direct sum :)] of one of these discussions, though I'll never know for sure. I ran into someone at a conference in Maui in 2000 who thought I was at Georgia Tech because I looked familiar. I knew he was because he was an AMa postdoc at Caltech when I was, so I told him that was why I looked familiar. (This is when it helps that there are only 2 graduates in the department a year and only just now have they finally reached 100 undergrad alums in its whole 50 year history.) We had a chance to talk several times, including at my poster. I expressed my interest in Georgia Tech and at that conference and at a later one, he indicated I should let him know when I was applying so that he would make the relevant faculty members aware of the application. (At this point, I am not privy to the events, but just getting one's portfolio examined seriously is a big step with there are N >> 1 other applications being sent directly to a department.)
For conferences, if there is on you want to attend, don't be afraid to ask your advisor about it. My advisor didn't have any money to send me, but Cornell did---up to one conference per year for up to $600. I found a conference to attend every year, and I also got a couple small funding awards directly from SIAM. I used my prize money for an award I got from SIAM to funding travel to other conferences (and the award included free attendance to a particular conference---it was at that prize winner reception that I met Cleve Moler, by the way), and I even spent some money out of pocket to make sure I could go to conferences I felt were important. (I was less social than I should have been at many of them, but that's a separate issue.)
In terms of number of places, I applied to something like 50 postdoc positions and 20 regular faculty ones. I applied for a regular faculty job in MechE at UIUC (and was interviewed) but everything else was math, physics, or applied math. At certain places (such as Georgia Tech), I applied to multiple groups. In fact, my hiring at GT did involve communication between relevant people in math and physics. (The program through which I was hired in math was for US citizens, so that's why the money came from math. Then the physics side could hire somebody without such a restriction, and I could be in both groups and have all the interactions with both that I wanted. It was a very good arrangement.)
OK, so I don't know if I answered every question Wren had (I doubt I did), but let me know specifically what else I should mention, and I'll try to say something useful. I know that I had to do all this stuff without my advisor (because he was out of touch with the greater research community), and while I can't prove what efforts led to what, you never know who is going to see your name in the hat and have some vague recollection of having seen it before. The more, the better.
I know there are a lot of extraneous details here, but I wanted to stress the conference thing here for people earlier in their graduate school careers.
Also, maybe Justin can add some useful stuff here, as he's also gone through the postdoc job search and can certainly pick up on stuff that I neglected or was just different from what he experienced.