Why "sudo apt-get install" doesn't find a package?

I am getting this error:

sudo apt-get install emacs23
Reading package lists... Done
Building dependency tree       
Reading state information... Done
E: Unable to locate package emacs23

Moreover, I ran:

sudo apt-get upgrade
Reading package lists... Done
Building dependency tree       
Reading state information... Done
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.

I have the latest public release version 12.10 Quantal Quetzal of Ubuntu.

You need to update your package lists.

Run:

sudo apt-get update

Then try again. That will fix everything.

You see, when Ubuntu software developers write their software, they send it to the Launchpad servers, where they compile and process the code. Once the code has been successfully compiled, the new package replaces the old package, and the package lists are updated to reflect that change.

Note that it's just the package lists on their server, not your computer. sudo apt-get update fetches the latest package info from the servers, at which point your computer processes it.
The command sudo apt-get upgrade checks the package lists (the ones stored on your computer) and compares the software in the package list with the actual versions you have installed. If any of your software has a version newer than it listed in the package list, it will download and install it.

Running sudo apt-get install <PACKAGE> checks your package list for that software. If found, it downloads and installs it.
(note that the package lists do not contain the software themselves - only the name, version, and the URL to download the software.)

Anyway, I hope my little speech helped you understand Ubuntu's package system a little better!