it's not an ubuntu package that you need to install, it's a php extension. Unfortunately the only way to add an extension to php is to recompile php with the needed extensions. It's not the easiest task, but it's not impossible. If you're comfortable with ssh, or at least know how to use it, then you'll be fine.
Here's a guide from DreamHost on how to do it:
http://wiki.dreamhost.com/Installing_PHP5Even if you're not using dreamhost it's the same basic principle. Just make sure that you add --with-zip and you're set.