Originally Posted by Varius

You need a Yahoo Developer ID first, which you can apply for if you don't have one. Once you have one though you can use it for all your new sites.

From their page:

Site Explorer API: Notifying Yahoo of Changes
Tell the Yahoo! Index when you have new content available.

The Update Notification service allows you to notify Yahoo! when your site changes. You may notify us about a single page, or a set of pages that need attention.

It works on new sites, I used it on one last week and it was in Yahoo in about 4 hours.