スタートアップ登録をするのはとても簡単。
コード内に下記のコードを1行追加してあげるだけです。

NativeApplication.nativeApplication.startAtLogin = true;

起動時にこの1行を実行してあげるだけで、スタートアップに登録することができます。

しかし毎回起動時にこの処理が実行されるため、ユーザーがスタートアップから解除しても、ガジェットを起動するたびにスタートアップに登録されてしまうので、ユーザーにとってはとても迷惑なガジェットになってしまいます。

この問題は、FileやSharedObjectを使って回避することができます。

初回スタートアップ登録時にファイルを生成し、次回以降はファイルの有無でスタートアップの判断を行うようにすれば、この問題を解決できます。

※参考サイト
http://blog.doinet.co.jp/?eid=864980
http://maxfactory.sakura.ne.jp/blog/2008/08/air2.php

WinXP＆Macでも検証しましたが、問題なく動作しました。

ただし、インストール時にスタートアップ登録の選択をインストーラーに持たせることはできないみたいですね。