Firestarter does not appear to have an option to enable it to run at Ubuntu startup. Is their a specific setting in Ubuntu that I need to edit to enable this?
The linux firewall is actually a feature of the kernel, and firestarter/etc are essentially just graphical configuration tools. So as long as firestarter is saving its configuration, those rules should be enabled on boot. http://www.fs-security.com/docs/faq.php#reboot
However, you are probably asking about getting a system tray icon, which is covered by the firestarter FAQ: http://www.fs-security.com/docs/faq.php#trayicon