AFAIK, this can only be set when a program would otherwise be denied access according to the current rule set (not if it would be allowed), so it should fire for new programs requesting Inbound, but not Outbound connections.
Control Panel > Windows Firewall > Change Notification Settings (left panel). You'll see "Notify me when Windows Firewall blocks a new program" option.
<del>I haven't tested this, but, by default Windows Firewall allows Outbound connections if none of the rules match (so for a new program). Perhaps, if you change the default behavior to Block, it would always ask you for both inbound and outbound connections. You can change that under Control Panel > Windows Firewall > Advanced Settings (left panel) > Windows Firewall with Advanced Security on Local Computer (this might vary, but it's the top item in the tree) > in the Overview section click Windows Firewall Properties link. You'll be able to set default behavior for various network profiles (public, private, etc.)</del>
Based on discussion here and personal experimentation, that notification is only shown for blocked inbound connections. It is not shown for outbound connections even if these are blocked by the default setting.
There's also some discussion here: http://superuser.com/questions/217551/how-can-i-configure-the-windows-7-firewall-to-prompt-me-on-outbound-traffic