The best Android VM at the moment is Nox, but it is windows only. (Fails under Wine).

It can be downloaded from http://en.bignox.com

Installation is straight forward.

Once installed, the following should be configured:

Enable root

set display to 800×600

disable resize

The VM files are stored in C:\Users\username\AppData\Roaming\Nox\bin\BignoxVMS

Screenshots are saved in C:\Users\username\Nox_share\Image

Install virtualbox on Linux using:

sudo apt-get install virtualbox virtualbox-qt

create default vm directory in home directory

mkdir ~/VM

Copy the Nox VMs into this directory.

Start virtualbox

In virtualbox, click on machine, add, navigate to ~/VM and add the vbox file of the first VM. Repeat with any additional ones.