1) Go into the app store.
2) Click on the category you're interested in on the left (eg, "all iphone apps")
3) Set "Sort By:" to "Release Date" at the top right corner.
4) Voila! The new stuff is listed first.
Just so you know, this doesn't totally work; there's a lot of new apps that pop up with old release dates, and they just get lost in the shuffle. Not sure why.