Mike Chambers has posted some very interesting information about Growl notification support over on his blog. This basically means that with the help of the Growl team, they have created a way for AIR applications to display messages via Growl, without Java or other external apps installed on the users system.
Update: It seems there is also a project for Windows notifications. Maybe this will be added to AIR soon as well.
