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:
Presumption: Android SDK 32 bit version is installed
On my Ubuntu 12 64 bit OS, I did not have to install any of the packages mentioned in the previous comments. Install the following using Android SDK Manager -
Under Tools: Android SDK Tools Android SDK Platform-tools Latest Android SDK Build-tools
Under the latest Android API (in my case, Android 4.3 (API 18)): SDK Platform ARM EABI v7a System Image
Under Extras: Android Support Library
Warning- I had earlier tried using the ia32-libs package. It installed successfully and I was able to run my Android apps. However, if I restarted the machine, it would never boot. Therefore, I suggest refraining from installing ia32-libs package. If it worked for you then great. Maybe it was an issue restricted to my PC then.
A slight twist on the above Q and A: I'm running Debian Wheezy (7.0) on a 64-bit System76 laptop, I had already enabled multiarch and most of the native Android tools seemed to run fine...until I tried building an app. The build failed because one of the resource utilities needed (a 32-bit) libz.so.1.