Use this command to search for it
apt-cache search postgis
This should return this, on Karmic, or something close:
osm2pgsql - Openstreetmap data to PostgreSQL converter
libpostgis-java - geographic objects support for PostgreSQL -- JDBC support
postgis - geographic objects support for PostgreSQL -- common files
postgresql-8.3-postgis - geographic objects support for PostgreSQL 8.3
To find more info, use apt-cache showpkg postgis this will show you, the version and what it depends on:
Package: postgis Versions:
1.3.5-1ubuntu2 (/var/lib/apt/lists/us.archive.ubuntu.com_ubuntu_dists_karmic-updates_universe_binary-i386_Packages)
...
Reverse Depends:
postgresql-8.3-postgis
With a little bit of research you'll find some posts about postgis 1.3.5, and postgrsql 8.4, it aparently didn't build cleanly and required patching, Postgis 1.3.6 makes special note of build improvements against 8.4 in the build notes
- Improve PostgreSQL 8.4 compile support (Talha Rizwan, Mark Cave-Ayland)
per the 1.3.6 docs.