Sensors to detect and measure movement
How much cpu do you already have available (if any)? 

Try Googling for "optical flow" - the hardware in optical mouses uses very low resolution cameras (8x8 or 16x16 pixels) and create sub millimeter resolution xy data from them. There's a bunch of optical flow stuff in OpenCV (which is exposed in the Processing OpenCV library), but I haven't used the optical flow functions myself. You'd then have the problem of getting the camera data off the object into a machine running the OpenCV code. Another option would be have a camera above the device/surface and use object tracking (which I'd also jump towards OpenCV for first).