Chez OVH, de ce que j'ai vu, il faut ajouter les repos non-free dans le source.list, sinon ça les installe pas...
nano /etc/apt/sources.list
puis coller à la fin :
deb http://ftp2.fr.debian.org/debian/ squeeze main non-free
deb-src http://ftp2.fr.debian.org/debian/ squeeze main non-free
et enfin
aptitude update
Après ça, tu pourras normalement faire ton
aptitude install unzip unrar