Try first running 'apt-get update' and then 'apt-get install mkisofs'. If it still does not work, you propably don't have correct source entries listed in /etc/apt/sources.list (it tells apt-get where to download all the programs from).
Try adding something like these three lines to /etc/apt/sources.list if they don't already exist:
deb
http://http.us.debian.org/debian stable main contrib non-free
deb
http://non-us.debian.org/debian-non-US stable/non-US main contrib non-free
deb
http://security.debian.org stable/updates main contrib non-free
(im guessing that you are using stable version, which is the default. If you are not, change stable to testing or unstable accordingly.)
Then run 'apt-get update' again and after that 'apt-get install mkisofs' should work or at least give you a different error