Unlike software for Windows or OS X, you can't simply drive over to your local big box store and make the purchase of a desired Ubuntu software. Instead, you will find most of the software you're looking for within the Ubuntu Software Center. Because of this, it'll be your primary area for discovering new Ubuntu software titles.
That said, there are other places around the Web you can check out if you're so inclined. The first one I like to visit occasionally is Google Code. Simply type in a query of the type of program you're looking for, along with the word Ubuntu. You'll find both new software titles you've never heard of, along with some familiar software ones to scour through.
Unfortunately, the second source for discovering new software doesn't present nearly as cleanly after searching Ubuntu (software type). Despite that small issue, if you're willing to do some browsing, SourceForge will offer you a number of useful Ubuntu compatible programs to skim through. As with Google Code, however, apps in SourceForge may still be under heavily development and are often less than user-friendly.
Now I realize that these methods aren't anywhere near as elegant as using the same search terms within the confines of the Ubuntu Software Center, but this approach does lead to software discoveries you might miss out on otherwise.
One last bonus tip: Did you know that you can create local desktop shortcuts to your favorite Web applications using the Google Chrome browser? For example, if I wanted an executable shortcut that basically provided me with windowed access to Google Calendar, I could create it by doing the following:
In this article, I've shared some of my favorite applications that I use every day. Some of them may be familiar, but I'm willing to bet that some of them are new Ubuntu software discoveries from your perspective. I also took this as an opportunity to pull back the curtain and share how I personally discover new software titles using very basic techniques that anyone can duplicate.
But perhaps the biggest takeaway I have to leave you with is this: More often than we realize, new software discoveries take place out of a need that wasn't there yesterday. For example, if I never needed a calendar application on Ubuntu, I might not have ever thought to scour the various application sources on the Web to see what's available. But once I realized that I really wanted a worthwhile calendar application, the tips shared above made the process simple.