My computer is a Sys76 Lemur running Maverick, and my phone is a Nexus S running stock Gingerbread. I want to set up to use ADB (android debug bridge). I installed the Android SDK per instructions on the SDK website, but ADB doesn't work. Can someone help me with directions that are specific to Ubuntu?

Install adb & fastboot via PPA

You can install from the WebUpd8 PPA which support both 32-bit and 64-bit. Granted you can install directly from google. But I prefer to use PPAs to keep everything up to date.
Works for Ubuntu 11.04, 11.10 and 12.04.

sudo add-apt-repository ppa:nilarimogard/webupd8

sudo apt-get update

sudo apt-get install android-tools-adb android-tools-fastboot

Source: Install ADB And Fastboot Android Tools In Ubuntu Via PPA

Install Android SDK via PPA

If you want to install the SDK which will allow you to update everything you can install via the upubuntu ppa.

So first thing is to add the ppa.

sudo add-apt-repository ppa:upubuntu-com/sdk

sudo apt-get update

sudo apt-get install android-sdk

Only issue at this point is that android-sdk needs to be run as root. Well the link in the menu didn't do much. So I updated the link in the menu, you can also run:

gksu android-sdk

From there you will need to install "Android SDK Platform-Tools" I also recommend updating "Android SDK Tools". You can deselect anything else you don't need.

Now you will need to set your environmental variables.

First you will need to make everything executable.

sudo chmod -R 755 /root/android-sdk-linux

Now to add the variables.

nano ~/.bashrc

Add these lines (at the top)

#AndroidDev PATH

export PATH=${PATH}:/root/android-sdk-linux/tools

export PATH=${PATH}:/root/android-sdk-linux/platform-tools

Source: Install Android SDK Manager (Revision 20) From PPA On Ubuntu 12.04/Linux Mint 13


Source: AndroidSDK - Community Ubuntu Documentation

Ubuntu 14.04+

Since Trusty the android-tools-adb and android-tools-fastboot packages in the Universe repository provide, respectively, adb and fastboot.

To install them:

• Enable the Universe repository: sudo add-apt-repository universe
  


• Update the APT cache: sudo apt-get update
  

To install adb:

sudo apt-get install android-tools-adb

To install fastboot:

sudo apt-get install android-tools-fastboot

I'm only guessing but perhaps you need to make sure Ubuntu is looking in the right place. As it says on the website, make sure you have added the directory that adb is located to your $PATH by adding export PATH=${PATH}:/usr/local/src/android-sdk-linux_x86/tools & export PATH=${PATH}:/usr/local/src/android-sdk-linux_x86/platform-tools to your .bashrc and running source .bashrc

@mywebslave answered it perfectly, I just want to add one more thing to that. If you're running a 64 bit machine and doing an offline install, you may have to install the 32 bit compatibility libraries as mentioned here.

sudo apt-get install ia32-libs

Update: The above command works only if you're running 13.04 and below. For newer versions ia32-libs has been replaced by other packages. See here.

sudo dpkg --add-architecture i386

sudo apt-get update

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

2017-Oct update

You don't need to install any package on Ubuntu 16 to get ADB working. No setup is necessary.

Simply download the official SDK Platform-Tools for Linux from Google and extract adb and fastboot from the zip file.