How to detect movement of an android device?

Definitely work with the accelerometer:

// Start with some variables
private SensorManager sensorMan;
private Sensor accelerometer;

private float[] mGravity;
private float mAccel;
private float mAccelCurrent;
private float mAccelLast;

// In onCreate method
sensorMan = (SensorManager)getSystemService(SENSOR_SERVICE);
accelerometer = sensorMan.getDefaultSensor(Sensor.TYPE_ACCELEROMETER);
mAccel = 0.00f;
mAccelCurrent = SensorManager.GRAVITY_EARTH;
mAccelLast = SensorManager.GRAVITY_EARTH;

// And these:

@Override
public void onResume() {
    super.onResume();
    sensorMan.registerListener(this, accelerometer,
        SensorManager.SENSOR_DELAY_UI);
}

@Override
protected void onPause() {
    super.onPause();
    sensorMan.unregisterListener(this);
}

@Override
public void onSensorChanged(SensorEvent event) {
    if (event.sensor.getType() == Sensor.TYPE_ACCELEROMETER){
        mGravity = event.values.clone();
        // Shake detection
        float x = mGravity[0];
        float y = mGravity[1];
        float z = mGravity[2];
        mAccelLast = mAccelCurrent;
        mAccelCurrent = FloatMath.sqrt(x*x + y*y + z*z);
        float delta = mAccelCurrent - mAccelLast;
        mAccel = mAccel * 0.9f + delta;
            // Make this higher or lower according to how much
            // motion you want to detect
        if(mAccel > 3){ 
        // do something
        }
    }

}

@Override
public void onAccuracyChanged(Sensor sensor, int accuracy) {
    // required method
}