All amd64 (i.e. 64-bit x64) processors can run 32-bit x86 binaries. Also, on most operating systems, you can run x86 programs on an amd64 OS. So it is often possible to deploy x86 binaries on amd64 processors.
Whether it's desirable to do so is a different matter. 64-bit OSes often come with a restricted set of 32-bit libraries, so if your program uses some uncommon libraries it will be easier to install a 64-bit executable. Depending on your application, there may or may not be a performance advantage to 32-bit or 64-bit binaries.
If you decide you want to deploy 64-bit executables, you'll need a cross-compililation environment for the amd64 (a.k.a. x86_64) architecture running on an x86 architecture. This means both a compiler, and static libraries to link against.
A gcc installation can share frontends and include multiple backends. But not many distributions ship with amd64 development tools on x86 platforms, so you may have to get your own (gcc is fairly straightforward to cross-compile). The same goes for libraries to link against (of course, once you have the compiler, you can recompile them from source).
As an example, Ubuntu 10.04 on x86 comes with a “multilib” version of gcc and an amd64 backend, plus a small set of 64-bit development packages (libc6-dev-amd64 Install libc6-dev-amd64 http://bit.ly/software-small and depending and dependent packages).