iTunes 7.7 became available last night and with it, the capability to buy applications to put on your iPhone. Well, you can't actually put them on your phone yet, but you can buy/download them. Here's a link to all iPhone Apps and here's a link to just the free ones. I can't seem to get the link for the main store's page, but the easiest way to get there is to click on "Applications" in your iTunes Library and click "Get More Applications".
The new iPhone software will likely be out later today so that you can actually install and use these apps.
Update: Here's the link for the iPhone Apps Store. (thx, carl)