Ubuntu has a good community-sourced HOWTO on this.
The repository keeps track of what the latest version of a package is, but your host has to get that information so it can pull the latest version. When you
apt-get update you're pulling a fresh copy of the list of all available packages, not just the ones you installed. Running
apt-get upgrade uses your local copy of the list, compared against the list of what you have installed, to decide what packages to download from the repository.
Whenever you run
apt-get upgrade, it uses the current (i.e. last downloaded) local copy of the package list to make decisions against. To make sure your local copy is fresh, you should run
apt-get update before upgrading, and after adding any new repository location.
In most cases (see the link), it's a good idea to use
apt-get dist-upgrade instead of