Addition 2018: The MiKTeX console
In 2018 a new tool, the MiKTeX console, appeared which unifies all the three previously used tools (settings, package manager, update manager).
You can check for updates, install new packages, add local roots and run most of the maintainance tasks with the console. Tabs to manage formats and languages have been added now too.
The console can operate in two modes (admin and user) and according to the documentation will ask on multiuser installation which mode you want to use. As described below you will need both modes.
Synchronization of the repositories can now be done through the tasks menu with the entry tasks->Update package database.
The FNDB can be updated with tasks-> Refresh file name database.
New in the tasks menu is the entry to recreate the font maps. This means that is no longer necessary to run updmap on a command line. tasks->Refresh font map files can be used instead.
Some documentation is here https://miktex.org/howto/miktex-console
Edit 2018: Windows and Linux
When I wrote this answer MiKTeX did run only on windows. Now a Linuxversion appeared. Be aware that things can be different there, e.g. the installation needs some special steps (https://miktex.org/howto/install-miktex-unx). Check the documentation!
Admin + User mode
If you have an multiuser installation you will have to maintain miktex in both modes. The admin mode alone can't do everything, it can't update packages installed by the user, it can't update formats and FDNB and map-files owned by the user.
So run the update manager in both modes and synchronize both package managers. Sometimes you will also have to create formats as user and update map-files (see below).
Synchronization
Miktex has an offline database which contains informations about available packages, their content and how to install them. Miktex needs such an offline database for the on-the-fly installation: Beside other problems it would slow down the compilation a lot if miktex would download the informations every time a file is missing.
When new packages are added to the online repositories, or if for some reason packages are rearranged or renamed the offline database on your PC is no longer up-to-date and you should "synchronize" (menu repositories in the package manager). If you have multiuser installation synchronize in both package managers (admin + user). As you can't know if this is the case you should use sensible rule of thumbs: Synchronize every month, if the update manager has removed some package, before running a lot of updates, if you are looking for a new package, if you get curious errors.
Updates
You should run regularly the update manager in admin + user mode to check for new packages. Before clicking on the "update" button, use your brain: updates do change the system and so can break it. Don't update when you don't have the time to handle problems. Don't update if packages are removed and you don't understand the implications. It doesn't do any harm to wait some days (I have miktex on three systems and their age differ by weeks).
FNDB + formats + Map-files:
In general it is not necessary to do something about it if you install packages with the package manager.
But there are exceptions:
FNDB
If you install files manually you should always update the FNDB (in admin + user mode if you don't know which one is the right one), it doesn't do harm to do it when miktex doesn't seem to find something installed.
Formats
User formats (created with the button in the user version of miktex settings) wins over admin formats. The update manager (admin) can't update such a user format so you will (sometimes) have to do it yourself if you have such formats by clicking on the update formats button in miktex settings (user version).
In the format tab of miktex settings you can exclude and include the formats you want to create. Formats that are excluded will never be updated automatically. So if a format doesn't change check its status.
Sometimes miktex forgets to trigger the format generation after a update of base files. Then you should update the formats manually in miktex settings (admin or user depending on the location of the old formats).
The creation of a format can fail (this doesn't happen often). In this case build one failing format from the format tab in miktex settings, copy the error message and ask for help.
Map-files
In quite a number of multiuser installation the on-the-fly installation created user map-files. These must be updated manually by running updmap on a command line after installation of packages with type1-fonts.
Critical Updates
Critical updates are updates which change core miktex packages (those starting with miktex- in the list).
It is difficult to impossible to revert the installation of the core packages. If after such an update a binary is broken it can impend your work heavily. So consider carefully if it is the right time to do the update. If you are in a production environment it is a good idea to wait a bit and check the mailing list and the bug tracker for reports.
In some cases such updates also need some new packages, e.g. newer versions of some .dll or some new tool. The update manager will not show you the new packages. It will also not warn you that these packages are needed and should be installed.
When you see an update list that looks as if it could be critical, it is a good idea to first start the package manager ((admin) in multiuser setups), synchronize the data base (menu repositories), check if there are uninstalled miktex-packages and to install them.
If you forgot this and miktex fails after such an critical update: Don't panic. You normally can install the missing packages with the command line version of the tools, or even manually after a download from CTAN.
miktex-etex-basebefore (without the versioning), IIRC.:)