I finally got around to setting up the Banshee Remote Android application today, and I must say, its quite an impressive ~40KB apk. It was developed by Nikitas Stamatopoulos, and instructions for setup, as well as download links for the .apk and source code, etc. are available on his website.
Banshee Remote on the Android Market is currently version 4.0, and you'll want the newest Banshee release (v2.0).
I have the Remote set up on my HTC Evo 4G using the WiFi connection to my 2Wire UVerse gateway allowing me control over the Banshee instance on my Ubuntu 11.04 desktop. I'm doing everything over the local network, in my case, without dealing with any external IP settings.
Overall, I'm very satisfied with the quality and simplicity of this application, and would recommend it to any music-lover with an Android device and a Linux PC. Props to Nikitas and his associates on a job well done. It would also be awesome to see some playlist integration and/or different shuffle options in a later release.
