For a Debian installer script, if there is an error within the postinst script or the user uses Ctrl+C to kill the process, is it possible to have the entire install be rolled back? It looks like even if I return a non zero exit code, it still leaves the program installed.
No.
Well, it's probably possible, because the postinst runs as root and can do all sorts of tricky stuff to subvert the system. But dpkg tries to protect against this as much as possible using locks, because maintainer scripts should not ever change the "desired" status of packages.
I haven't verified this, but I would guess that if you cancel a postinst script with Ctrl+C, it counts as a postinst failure, and the package is marked as being in the half-configured state. So, it's not left fully-installed, exactly, but yeah, it might be hard for the user to tell the difference.
So, some potential solutions for you:
If your package provides a service, you could have a flag (e.g., a file in some place like /var/lib/$yourpackage) which is set only when the package is fully installed (at the end of the postinst). The service would check for this flag on startup, and if it's not present, the service would not start, and might even print a warning message about not being fully installed. This solution would be similar in some respects to having the package totally uninstalled. Remember to unset the flag or remove the file at in the prerm and at the beginning of the postinst (in case a Ctrl+C occurs during an upgrade instead of on the first install).
You could catch the Ctrl+C (SIGINT) in the postinst, and print a message saying something like "This package will be left in the Failed-Config state. To remove it entirely, run (dpkg -P/apt purge/whatever). To attempt to complete installation, run dpkg --configure -a." (Then exit the postinst with a nonzero exit code, so that dpkg knows about the failure.)
If you are in a position to do this, make your users more aware of when they have brokenly-installed packages, so they can make the decisions about reinstalling or removing quickly.
You could take whatever thing in your postinst is most likely to be Ctrl+C'd, and move it to the preinst. If the preinst fails, then dpkg will call the postrm with the abort-install action. The postrm is expected to clean up anything that the preinst already did. If the postrm succeeds, then the package is left cleanly and entirely uninstalled. Of course, if this step of the postinst needs the files from your package to be unpacked and present, this isn't really an option.