Lots of answers so far, which are all excellent pointers to API's and tutorials. One thing I'd like to add is that I work out how far the markers are from my location using something like:
float distance = (float) loc.distanceTo(loc2);
Hope this helps refine the detail for your problem. It returns a rough estimate of distance (in m) between points, and is useful for getting rid of POI that might be too far away - good to declutter your map?