And there's always apt-cache policy <package-name> (no sudo needed).

Not installed:

oli@bert:/$ apt-cache policy gnuift

gnuift:

  Installed: (none)

  Candidate: 0.1.14-11

  Version table:

     0.1.14-11 0

        500 http://archive.ubuntu.com/ubuntu/ oneiric/universe amd64 Packages

Installed:

oli@bert:/$ apt-cache policy firefox

firefox:

  Installed: 8.0+build1-0ubuntu0.11.10.3

  Candidate: 8.0+build1-0ubuntu0.11.10.3

  Version table:

 *** 8.0+build1-0ubuntu0.11.10.3 0

        500 http://archive.ubuntu.com/ubuntu/ oneiric-updates/main amd64 Packages

        500 http://archive.ubuntu.com/ubuntu/ oneiric-security/main amd64 Packages

        100 /var/lib/dpkg/status

     7.0.1+build1+nobinonly-0ubuntu2 0

        500 http://archive.ubuntu.com/ubuntu/ oneiric/main amd64 Packages

Or dpkg: dpkg -l | grep -E '^ii' | grep <package name>. When it's not installed it won't show output. When it is, it'll show something like:

oli@bert:~$ dpkg -l | grep -E '^ii' | grep firefox

ii  firefox                                                     8.0+build1-0ubuntu0.11.10.3                            Safe and easy web browser from Mozilla

ii  firefox-branding                                            8.0+build1-0ubuntu0.11.10.3                            Safe and easy web browser from Mozilla - transitional package

ii  firefox-globalmenu                                          8.0+build1-0ubuntu0.11.10.3                            Unity appmenu integration for Firefox

ii  firefox-gnome-support                                       8.0+build1-0ubuntu0.11.10.3                            Safe and easy web browser from Mozilla - GNOME support

ii  firefox-locale-en                                           8.0+build1-0ubuntu0.11.10.3                            English language pack for Firefox

It's obviously a fuzzier search but handy if you're not sure which package you're looking for.

For manually installed things...

A bit harder but if they're on the current path, you could just run them. That's a bit of mission so I'd rather just run:

oli@bert:/$ which chromium-browser

/usr/bin/chromium-browser

And:

oli@bert:/$ which gnuift

# returns nothing

Which is better?

That depends on the sanity of user. There's nothing to stop somebody installing something called chromium-browser that isn't Chromium. They could even package it up incorrectly and install that. Neither method can be 100% certain.

But assuming the owner is sane - packages should be good enough for most people.