If you have a fresh system and want to get debian on it, here are is a
small guide on how I managed to get a debian with 64-bit kernel and
toolchain. Footnotes for URLs.
The hardware: Tyan Thunder K8S with a cd-rom drive and an ide harddrive.
It has an onboard broadcom dual gigabit ethernet supported by newer tg3
drivers (1.2 doesn't seem to work, 1.5 does).
1. Install woody from cd.
2. Upgrade kernel to one with working tg3 driver to get network
connectivity. I did this by compiling from kernel-source-2.4.21
as included on the first iso from sarge snapshots.
3. Build a kernel on an existing amd64 system using:
* patched kernel-package
4. Install the kernel
4.1 scp the kernel over from the system in (3).
4.2 download modutils for amd64 and put it somewhere good (not /tmp)
4.3 install the kernel (dpkg --force-architecture -i ...)
4.5 install modutils from step (4.2) (dpkg --force-architecture -i ...)
4.7 cursing discover that the eth1 you had connected while running the
kernel from (2) is now eth0 and rewrite /etc/network/interfaces
4.8 ifup and be happy
5. Install the biarch debs as needed/wanted 
6. Install dpkg with amd64 support so that you won't have to type in
that --force-architecture all the time
7. Done, or iterate step 5 until you can compile stuff with gcc -m64.
If you have a similar enough system to mine, this might replace step 2&3:
3: ssh ravel.hpc2n.umu.se, ask me for an account if you want one
The cursing in step 4.7 might not be necessary if you don't do a couple of
kernel install cycles before you figure out what happened. :)