If I'm right, Firestarter is basically just a front-end for creating an iptables script. It means that
iptables, which is the "Linux firewall", handles the firewall rules, but for it to work it needs the rules first fed to it; Firestarter is a graphical program which you use to create the rules, and once you "save" them (or whatever the program calls it), Firestarter creates a list of iptables commands which it runs, creating the appropriate iptables settings. Then it saves this file so that iptables uses these rules every time you boot your machine. So you don't have to run Firestarter all the time, just when you alter or create "a firewall", i.e. create the rules. After that you just save the configuration and Firestarter creates the file for iptables and that's it.
I'm not 100% sure about how it exactly works, since there are a few ways to achieve the result, but I could imagine that Firestarter without extra options just runs the program, which silently feeds iptables the rules. To get the graphical user interface you probably need to give it an extra option to get the program to show the UI, but that's not needed as I already said. If running plain Firestarter (without options, that is) produces no errors, it probably means that the program starts, gives iptables the instructions you created earlier and exits with exit code 0 (success). Therefore you don't need to create that extra startup script, the one existing should already do the job (it's in rc2.d-rc5.d because it is meant to be run at each runlevel from 2 to 5 -- runlevels 1 and 6 are for shutdown/reboot so they're not interesting in this case).
What does the already-existing Firestarter startup script have inside, have you looked at it?
Code:
more /etc/rc4.d/S20firestarter
My guess is that that just "takes the iptables rules in use" at every bootup, once you've created them first (one time only).
You don't actually need Firestarter if you're ok with
iptables commands; you can just as well write a shell script that runs the appropriate iptables commands and either set it to be run at each bootup or use iptables-save to produce a file which you can then, for example, put in some place where you like to store your firewall config, and then make some startup script read it at bootup. That's what Firestarter does, except that it includes a "nice" interface too (in my opinion iptables' interface is just all right, it's got everything you need, nothing less and nothing more).
Iptables is in your kernel, and in addition to that you have the userspace tool called iptables which you use to configure the rules (iptables can do much more than just firewalling, by the way). Applications like Firestarter are just front-ends to iptables, not actual firewalls. Here's the process
Decide rules -> run iptables(userspace) to set them -> iptables(in kernel) uses them -> load them at boot
...and here's what happens with Firestarter:
Decide rules -> "create them" with Firestarter -> it runs iptables(userspace) to set them -> iptables(in kernel) uses them -> Firestarter created the script to load them at boot
As you can see, they're pretty much just the same. Except that I'm not sure if you can achieve everything with Firestarter that you could with iptables, but I might be wrong as well..
If I made some mistakes or wrong assumptions, please correct me, but I'm in the impression that this is the case. Some people have asked this same question earlier, and I think they were adviced not to run Firestarter during boot by themselves, it should handle the thing all by itself. You can check if it works like this: after bootup (without running Firestarter yourself) run, as root,
If the firewall is clean, i.e. "turned off", you should just get ACCEPT rules for INPUT, OUTPUT and FORWARD and nothing more. If your firewall rules are set all right, they should be visible in the output.