A new library to build heatmaps using android is provided at http://code.google.com/p/mapex/
The library not only provide a heatmap overlay that makes simple adding heatmaps to your projects but also some other nice enhancedments to the current android maps PAI:
- Area selection with drag and drop
- Zoom and Pan events
- Utility methods to work with geospatial data
- Clustering (soon)