Before I had gotten the Droid I had done a Google search on "Android Market." One site gave a few (and said you'd need to use your phone to find all). One they suggested was Carrr Matey which is a car location app. I downloaded that as soon as I got the phone and later on downloaded one called "Car Locator."
Carrr Matey is pirate themed. When you "Drop Anchor" it gets your GPS location and asks if you want a timer (for a parking meter). If you want to find your car later on you press "Find Vessel." You then get a selection of either Compass or Map. Compass is like Captain Jack Sparrow's compass in that it doesn't point North but to what you desire (in this case your car) it also gives distance. If you press Map, it'll give you walking directions on how to get back. You can find more information at Carrr Matey v1.5.9 Application for Android | Travel and is free.
Car Locator is not free (after 10 uses you have to pay $1.99, but it has more features). It works like Carrr Matey, but has a more sci-fi look to it. You can see a map all the time, or just a list showing how long you've parked, direction and distance. You can see that at Car Locator FREE v2.10 Application for Android | Travel
Both worked fine on the Droid.