Hi. I've been away for a few weeks but just wanted to pick this thread up again. You may have figured most of this out already.
The desktop file in /usr/share/applications is what icewm uses to put icons on the menu. I just installed VL6.0 Light in VirtualBox to check things out and I notice that you have to regenerate the menu each time you add an application. There's a command to do that on the System menu. After that the icon for Firestarter will show up on the menu under System. With XFCE, which I'm used to, the icons get added to the menu automatically.
If you are seeing an entry for Firestarter when you boot or shutdown then it's running. There is a script in /etc/rc.d/init.d for checking its status. As root in a terminal issue the command /etc/rc.d/init.d/firewall status and you should get a message saying that Firestarter is running. You can stop and start it in the same way.
If you want to see what the firewall is doing then just run the Firestarter GUI from the menu (or from a terminal) and look at the status and events tabs.
As I understand it, Firestarter (and Guarddog etc) are just GUI front ends for the built-in iptables which is really what's doing the filtering. Starting the firewall loads the appropriate kernel modules and if you do an lsmod as root in a terminal you will see several entries with iptables in their names when the firewall is running.
I have found that whatever front end you use for iptables you have to enable the firewall for the run levels you require, usually 2 and 4 I think. You do this in the services section of VASM. If you don't do this it won't be running after a reboot.
Hope this helps. If anyone has any corrections or amplifications please chime in, this area is still a bit fuzzy for me.