You can now build MSIs for Windows and DMGs for Macs with AIR that will bootstrap the runtime. That said, I haven't used that option.

Up until Craig's lawyers killed my app, I was using the flash installer that was seamless. Same sort of installation process can be seen on TweetDeck which uses AIR.