The recorder and microphone that I see most often recommended are the
Marantz PMD660 or 670 and the Sennheiser ME66 or 67, respectively.

I opted for slightly different equipment and am very happy with it. I used
a M-Audio Micro-Track, which may not be as robust as the Marantz but it is
smaller, and I find that important if I carrying it around all the time.
Its only shortcoming is that the battery is not replaceable, but it proved
enough for a day of intense work. Marantz now has a very small model too
(PMD620); I don't know it but looking at the pictures I see it only has a
small microphone jack, which may be less convenient for the type of
microphones we use.

I used an Audio-Technica AT835b microphone, simply because its technical
characteristics are similar to the Sennheiser's and it was cheaper. We
should not hold the microphone directly because then our body introduces
some low frequency sound. Because bird song is high-frequency, this is not
a big problem, and any simple hand held device will suffice. Optionally,
you may want one of those fluffy wind-shields, but those are big and
inconvenient to carry around, and for normal recording conditions the
standard sponge wind-shield that comes with the microphone is enough.

I bought all my stuff from amazon or from sellers at amazon, just because
it was the simplest way.

Additional suggestions, 2008 - anonymous

single-unit Foxpro FX3 remote control speaker (about $500)

good digital recorders which do not compress the sound files into MP3 format, are the M-audio MicroTrack II digital recorder (about $300 but has an internal rechargeable battery), and the Marantz PMD620 digital recorder (about $400, uses rechargeable AA batteries). Digital sound files can be downloaded directly into a hard drive and are immediately ready for analysis; they also contain time-stamp information.