Dispite what the accepted answer says in the comments, the correct way to install 'Memcache' is:
sudo apt-get install php5-memcache
NOTE Memcache & Memcached are two distinct although related pieces of software, that are often confused.
EDIT As this is now an old post I thought it worth mentioning that you should replace php5 with your php version number.