Squid 3.1 introduced support for IPv6, so there is a very good reason for an upgrade from Squid 3.0.
Unfortunately, there is no Ubuntu package for this version, not even in the upcoming Ubuntu release 10.04 Lucid Lynx.
For a while, I have been using the Debian experimental packages of Squid 3.1.0, compiled from source on Ubuntu 8.04. However, now a stable version of Squid 3.1 has been released, but there is no Debian package for Squid 3.1.1.
Therefore, I used the Debian package for Squid 126.96.36.199 as the base for building a package for Squid 3.1.1. I have published this package in source as well as built for Ubuntu 8.04 on amd64. There you can also find a package for libcap2, which is required by Squid 3.1 but not included in Ubuntu 8.04.
Of course, there is no kind of warranty for this packages, so use them at your own risk.