Android SDK on a 64-bit linux machine

On (K)Ubuntu you need following 32-bit packages:

sudo apt-get install libstdc++6:i386 libgcc1:i386 zlib1g:i386 libncurses5:i386

for running the emulator you need that additional package:

sudo apt-get install libsdl1.2debian:i386

Yes, it is. You need to install the ia32 libraries. Check out the Ubuntu Linux troubleshooting section.

apt-get install ia32-libs
apt-get install sun-java6-jdk

Android SDK requires:

• Fedora 17 64bit with Android SDK:

  sudo yum install glibc.i686 zlib.i686 libstdc++.i686 ncurses-libs.i686
  

• Fedora 20 64bit with Android SDK

  sudo yum install glibc zlib libstdc++ ncurses-libs mesa-libGL-devel adb
  

For Debian Wheezy you have to enable multiarch and then install the dependent libraries as listed in the other answers or as needed by the binaries from the tools or platform-tools directory:

sudo dpkg --add-architecture i386
sudo apt-get update
sudo apt-get install libc6:i386

For further libs check with ldd for referenced .so-files.

platform-tools$ ldd adb                       
    linux-gate.so.1 =>  (0xf77bb000)
    librt.so.1 => /lib/i386-linux-gnu/i686/cmov/librt.so.1 (0xf779b000)
    libncurses.so.5 => not found
    libpthread.so.0 => /lib/i386-linux-gnu/i686/cmov/libpthread.so.0 (0xf7781000)
    libstdc++.so.6 => not found
    libm.so.6 => /lib/i386-linux-gnu/i686/cmov/libm.so.6 (0xf775b000)
    libgcc_s.so.1 => /lib/i386-linux-gnu/libgcc_s.so.1 (0xf773e000)
    libc.so.6 => /lib/i386-linux-gnu/i686/cmov/libc.so.6 (0xf75db000)
    libdl.so.2 => /lib/i386-linux-gnu/i686/cmov/libdl.so.2 (0xf75d6000)
    /lib/ld-linux.so.2 (0xf77bc000)

So continue to install libncurses5:i386 and libstdc++6:i386 to be able to run

platform-tools$ ./adb 
Android Debug Bridge version 1.0.31
...