Предустановка Node.JS (минимальная необходимая версия 0.12): sudo apt-get install javascript-common build-essential nodejs sudo npm cache clean -f sudo npm install -g n sudo n 0.12.7
Установка, собственно, Appium через npm: sudo npm install -g appium

Установка Android SDK 7-й версии, рекомендуется 8-я:
Просто следовать инструкции https://developer.android.com/studio sudo apt-get install android-tools-adb

Подключение смартфона для работы с ним, выполнить действия указанные по ссылкам:
1. Using Hardware Devices
2. How to configure ADB access for Android devices?

adb devices — запускаем демона, смотрящего за подключёнными устройствами
adb devices -l — получить список подключённых устройств
adb logcat > logfile.txt — записать дебаг-лог с устройства, внимание, размер файла быстро растёт!
android — Запустить Android SDK Manager. Можно устанавливать/удалять плагины и версии Андроида к SDK.
android avd — Запустить Android Virtual Device (создаём/выбираем профили, параметры устройства, запускаем)

1. Предустановка: VirtualBoxsudo aptitude install virtualbox virtualbox-qt virtualbox-dkms
2. Пройти на страницу загрузки Genymotion и скачать подходящий вам пакет (расширение bin). Чтобы загрузка стала доступной — надо зарегистрироваться.
3. Дать права на выполнение скачанного файла:sudo chmod +x genymotion-2.6.0-linux_x64.bin
4. Распаковать его:./genymotion-2.6.0-linux_x64.bin
5. Запустить GenyMotion: cd genymotion ./genymotion
6. Здесь рассказано как настроить поддержку Google Play Services