Linux has been running on 64bit architectures like the DEC Alpha since the mid or late 90'ies or so. Several others are supported, including the Sun UltraSPARC, Intel's Itanium/Itanium2 and AMD's 64bit alternatives.
If you're looking to get an AMD64 system there is an AMD64-specific distribution from SuSE
has Mandrake Linux for AMD64 available for pre-order now. Debian
has ports for the IA64 (Intel Itanium), the Alpha and the SPARC. The Debian AMD64 port isn't released yet but work is underway.