SysVinit works like this. Initialization scripts for each package are located in /etc/init.d. Links to those scripts are located in /etc/rcS.d and /etc/rc[0-6].d. These links start with either S (start) or K (kill) and a 2-digit number.
When the system boots and the SysVinit process starts, it looks in /etc/rcS.d and executes scripts starting with S, ordered by the number. (I believe it passes the "start" argument to the scripts, but I'm not sure.)
After all /etc/rcS.d scripts are processed, the system begins moving into a certain runlevel. In Ubuntu, booting to the normal desktop, the default runlevel is 2. So SysVinit looks in /etc/rc2.d and
- stops all services with links starting with K, ordered by the number; and
- starts all services with links starting with S, ordered by the number.
If you've booted into Ubuntu's recovery mode instead, you'll be booting into runlevel 1. After all services are started, the system runlevel is officially set.
Finally, the system runs the /etc/rc.local script.
If you switch runlevels later, SysVinit runs the same basic process: it doesn't check /etc/rcS.d, but goes straight to processing the links in /etc/rcN.d (where N is whatever runlevel is being entered).
You could also write an Upstart script. I've written about Upstart previously, so check there for more details. Upstart scripts are kept in /etc/init; to write them, look over existing scripts to get a feel for how it works, and read the init(5) manpage.