This is an issue for closed source programs targeting multiple contemporary distributions, or for programs with long release cycles targeting multiple versions of distributions.
Hardware dependenciesGenerally a binary will be released for each architecture, but one still has to be wary of variations within an architecture. Talking the x86 architecture for example which has many variants, one can generate binaries optimized for a particular CPU, which will not work on other x86 CPU types. If you know your users' most common CPU types, then one can generate optimized binaries that degrade gracefully by running more slowly on less common CPU types by using the -mtune gcc compiler option.
Software dependenciesThe rule of thumb here is that, generally backwards compatibility is maintained by linux distributions but forwards compatibility is not guaranteed. I.E. it's better to build, or at least link your binaries, on older linux distributions, though that restriction can be worked around to some extent as I'll describe below.
There are also efforts in the form of the Linux Standards Base to aid applications to be binary compatible over various distributions. To that end the LSB maintains a utility to check applications for binary compatibility, and also applications that are LSB certified will be binary compatible within an LSB release set.
kernel dependenciesThere is no official Kernel ABI (Application Binary Interface), but generally great efforts are made to maintain compatibility. When this is not possible then glibc will usually abstract the applications from the details involved. Note glibc sometimes requires hints about what interface the application expects, through the use of the LD_ASSUME_KERNEL environment variable.
library dependenciesThis is generally the largest compatibility problem area. Now you may think that one could statically link an application, thereby including all logic within the binary and only depending on the kernel interface. This is not practical unfortunately.
Now larger libraries like glibc provide symbol versioning, so that interfaces used by the application can be easily checked at run time as to whether they're available or not. The developer can also easily check the symbol versions their application uses by doing nm binary | grep @@GLIBC_ | sort -t@ -k3,3. If there is a glibc version listed there that is too new for your dependency requirements, then there still is the possibility of using it if it can be inlined. Take the makedev() function for example, which if used, results in linking to gnu_dev_makedev@@GLIBC_2.3.3. If one turns on inlining of functions though, the dependency on glibc >=2.3.3 is removed as the logic is included directly in the binary.
For larger library interface changes, a new version of the library will be used, which presents a major problem for binary compatibility as an application can only be linked to one particular version of a library. Sometimes the distribution provides a "compat" package containing the required older version of the library. When this is not available the only option is to link this particular library statically into the binary. A commonly used library where this issue occurs is libcrypto from openssl whose library version changes often. This library can be linked statically using the following gcc/linker options: -Wl,-Bstatic -lcrypto -Wl,-Bdynamic. Note that the linking mode is reset to dynamic options so that any implicitly linked libraries are linked dynamically. Linking a library statically doesn't always suffice though, as it itself can use new glibc features. For example libcrypto on Fedora 7 is compiled with the -fstack-protector option, which introduces a link to __stack_chk_fail@@GLIBC_2.4. Note also that one is not allowed to statically link LGPL libraries unless there is an explicit clause allowing this.
Other tweaks may be necessary for forward compatibility, i.e. building on newer linux distributions while supporting older ones. For example the new dynamic linker hash used by default in Fedora Core 6, means all binaries produced on Fedora Core 6 and later give the confusing "floating point exception" error when run on systems with older glibc's (including Fedora Core 5). Personally I think this performance only change could have been gradually introduced, by including both hash formats for a while. To tell compilers on Fedora Core 6 and later to use the older style hash one passes the -Wl,--hash-style=sysv or -Wl,--hash-style=both option to gcc.