If it will work on a phone then there must be a way to work it on a N800. Looks like there is a special lite version.
http://www.pandora.com/on-the-go