You could either install the program every time you run Ubuntu Live, using another drive/partition and a quick install script, something like "sudo dpkg --install program.deb" should work.
Like another answer said, using a USB with "persistent" would work too, but be aware there was a bug in the persistence where after several reboots (took me a few weeks of daily boots to see it) where the persistent data would get corrupted. It was existing in some debian bug reports since 2007 or so, and still there in 2011. And of course, a CD would need a separate drive/partition to save the persistent data.
Or you could remaster a new Ubuntu Live ISO/CD/USB, a tool like remastersys should work, and there are other tools to do that too, but I don't know which are "easier" or "best".