The burgeoning market for Android apps and the open nature of the Android platform and Market have already attracted upward of 30,000 apps. It doesn't matter that the iPhone apps store has 10 times as many; 30,000 apps is plenty, really -- enough that your biggest problem in locating a good app for a specific purpose might be winnowing out the also-rans and the not-quite-what-I-had-in-minds.
Tip 1: Use AppBrain.com from your PC or Mac
I like finding apps online, but not necessarily from my phone. I can type a lot better at my computer. And as nice as Web browsing can be on an Android phone, for some inexplicable reason it just isn't as nice as browsing from a quad-core PC with a fast graphics card that is hard-wired to a cable internet connection.
The official Google Android Market (see Tip 3) is all well and good when you are using your phone, but from your PC or Mac, the Android Market website only displays "some of the featured and top ranked applications and games available on Android Market." These "top ranked" applications are often fairly good, but without comments and ratings you miss out on some important details, and without a search function you can't easily home in on what you want.
There's another alternative for finding Android apps online from your computer: AppBrain. As it says in the AppBrain FAQ:
AppBrain is a website for discovering Android apps. In addition to providing search and browse functionality, users of Android phones can download the apps they chose by simply clicking an install button on the site. AppBrain then stores the application in an application wishlist. A companion native Android app then lets the user efficiently make all the desired changes on the phone.
The applications come from the Android Market; AppBrain just offers another interface to the market.