What does it mean that a package is "set to manually installed?"

You can use sudo apt-mark auto $PACKAGES to mark packages as automatically being installed again, if you accidentally mark them as manually installed.

Automatically installed packages can be removed using apt-get autoremove (or using similar processes, e.g. via Synaptic).

If you install a package, all packages that that package depends upon are also installed. For example if you install the package vlc, it will automatically install vlc-nox. The automatically installed packages (in this case, vlc-nox) are set as "automatically installed" -- if you remove vlc, the package manager will suggest to remove vlc-nox as well (aptitude will do this automatically, if you use apt-get you can remove all automatically installed packages with apt-get autoremove).

Now, if you do apt-get install vlc-nox you will get the message that vlc-nox is now set to "manually installed", i.e. the package manager now thinks that you want that package specifically and not just installed it because vlc needed it. If you remove vlc, vlc-nox will therefore not be automatically removed.

This does not affect updates in any way.

It means that a package was manually selected and not automatically by another packages or a meta-packages. The difference it, that the latter can be auto-removed, when the package that triggered this install is not anymore present (after an upgrade, or because it was removed). A manually selected package should not be removed in this way.

This has no impact on the ability to upgrade package when such upgrades are available or the notifications thereof.