correct me if i'm wrong, but Adobe AIR currently only allows applications to have maximum size icon of 256x256.
update: AIR 2 still doesn't support importing 512x512 sized icons.
while larger icons are not officially supported by Adobe, until then, i've discovered that it's pretty easy to include your own larger sized icons for AIR applications with native installers - at least on .dmg installers for Mac OS X.
with Mac OS X, you can drag the installer out of the .dmg onto your desktop, right-click the installer application to "show package contents", jump thru the folders until you see Icon.icns and then simply replace that with your own Icon.icns file. after that, you can just repackage the installer into a new .dmg. it's kind of a hassle, but it beats having pixelated icons.
this method requires you to build your native installer with an icon, however, foolishly, the included .png icon is never deleted from the bundle by the installer, even though it's only used once to create the Icon.icns file. therefore, i suggest you only import a 16x16 .png white square with a tiny file size. if you try deleting it the installer will say the package is corrupt, which it is since the application.xml file refers to the included icon. removing the icon entry from the .xml will result in the installer not using your custom Icon.icns file.
for those who don't know how to make an .icns file on Mac. you can download/install XCode developer tools and use the included program called "Icon Composer". it's a basic drag-and-drop .icns file creator.
i'm not sure how this process can be emulated on Windows or Linux, so if anyone reading knows please post an answer.