Edit 2012-11-12: If you're interested in the newer problem of running PHP 5.3 on Ubuntu 12.10 Quantal, try this recipe.
Edit 2012-09-21: Isn't it about time you moved to PHP 5.3? Even though these instructions seem to work even for Ubuntu 12.04, it's really time for people to move on to PHP 5.3. If you're a Drupal user on Drupal 6, Drupal core and nearly all contrib are now just fine with 5.3.
Edit 2011-11-23: Since Ubuntu 9.10 (Karmic) is now out of support, the repositories to use for it have changed to old-releases.ubuntu.com. I've changed the karmic.list files attached. Please be aware that although 10.04LTS is still supported for years still, 9.10 is out of the support window, meaning that security issues in these packages will not be fixed.
Update: Look here to solve same problem with Ubuntu 10.10.
Lots of us are starting to run Drupal on Ubuntu 10.04 Lucid Lynx, and of course, Lucid comes with PHP 5.3, for which Drupal 6 is not yet ready.
I've seen a couple of fine recipes, but here's mine, with the files you need attached.
Update: You'll probably want to look at Khalid's more extensive discussion of various ways to do this.
Essentially, all you have to do is tell the apt system where to find Karmic packages and then tell it that you want it to use Karmic's PHP packages.
So put the attached karmic.list in /etc/apt/sources.list.d and the attached "php" into /etc/apt/preferences.d.
Then:
sudo apt-get update
sudo apt-get remove php5 libapache2-mod-php5 php5-xsl php5-gd php-pear php5-mysql php5-curl php5-memcache
sudo apt-get install php5 libapache2-mod-php5 php5-xsl php5-gd php-pear php5-mysql php5-curl php5-memcache
If you had not already installed apache, php, and mysql, you can do that with the above files in place and get the right versions without removing anything:
sudo apt-get update
sudo apt-get install apache2 mysql-server php5 libapache2-mod-php5 php5-xsl php5-gd php-pear libapache2-mod-auth-mysql php5-mysql php5-curl php5-memcache
Note that your php.ini will have been replace, so you have to reset custom settings like memory_limit.