Upgrading from drupal 8 to drupal 9 needs to be done with composer. 

Step 1: remove console

First, make sure you are on the latest version of drupal 8.

For a starter, make sure you remove drupal/console first (!). This will prevent you from having a loop in dependencies for the symfony package:
 

composer remove drupal/console

Step 2: Manually add/update the drupal versions in your composer.json

Manually add/update the drupal versions in your composer.json for:

"drupal/core-recommended": "^9.0",
"drupal-composer/core-composer-scaffold": "^9.0",

Also, if you still have drupal/core separate in your composer, remove it from composer.json.

If you have drush and devel, which are widely used, also manually edit the versions:

"drupal/devel": "^4.0",
"drush/drush": "^10.0.0",

The update command

composer update drupal/core-composer-scaffold drupal/core-recommended --with-dependencies

This resulted for me in the following:

 Problem 1
    - drupal/core-recommended 9.1.0 requires symfony/var-dumper v5.1.8 -> satisfiable by symfony/var-dumper[v5.1.8].
    - drupal/core-recommended 9.1.0-beta1 requires symfony/var-dumper v5.1.8 -> satisfiable by symfony/var-dumper[v5.1.8].
    - drupal/core-recommended 9.1.0-rc1 requires symfony/var-dumper v5.1.8 -> satisfiable by symfony/var-dumper[v5.1.8].
    - drupal/core-recommended 9.1.0-rc2 requires symfony/var-dumper v5.1.8 -> satisfiable by symfony/var-dumper[v5.1.8].

Debugging composer: the why command

For this, we have a 'why'-command to get more info on where the dependencies come from.

bash-$ composer why symfony/var-dumper
drupal/devel  2.1.0    requires  symfony/var-dumper (~2.7|^3|^4)
drush/drush   9.7.2    requires  symfony/var-dumper (^3.4 || ^4.0)
psy/psysh     v0.10.5  requires  symfony/var-dumper (~5.0|~4.0|~3.0|~2.7)

In this case it was clear that devel and drush are the ones that needs to get updated. We add them in our update command and run again:

composer update drupal/core-composer-scaffold drupal/core-recommended drush/drush drupal/devel --with-dependencies

Keep updating

This again results in new problems:

Problem 1

 - drupal/core 8.0.0-beta6 requires doctrine/common dev-master#a45d110f71c323e29f41eb0696fa230e3fa1b1b5 -> no matching package found.
    - Conclusion: remove composer/installers v1.9.0
    - Conclusion: don't install composer/installers v1.9.0
    - drupal/core-recommended 9.0.0-alpha1 requires composer/installers v1.7.0 -> satisfiable by composer/installers[v1.7.0].
    - drupal/core-recommended 9.0.0-alpha2 requires composer/installers v1.8.0 -> satisfiable by composer/installers[v1.8.0].

Now we add composer/installers to our update:

composer update drupal/core-composer-scaffold drupal/core-recommended drush/drush drupal/devel composer/installers --with-dependencies

Repeat this step until all the modules that return compatibility errors are resolved. You might end up with a long command of more than 10 modules!

There is drupal 9!

Finally, we see our drupal 9 arriving. 

  - Updating twig/twig (v1.42.5 => v2.12.5): Loading from cache
  - Updating symfony/yaml (v3.4.41 => v4.4.9): Loading from cache
  - Downgrading symfony/polyfill-php80 (v1.20.0 => v1.17.0): Loading from cache
  - Updating symfony/var-dumper (v4.4.17 => v5.1.0): Loading from cache
  - Installing symfony/translation-contracts (v2.1.2): Loading from cache
  - Updating symfony/validator (v3.4.41 => v4.4.9): Loading from cache
  - Updating symfony/translation (v3.4.41 => v4.4.9): Loading from cache
  - Installing symfony/service-contracts (v2.1.2): Loading from cache
.........

Conclusion

It is harder than expected, and you should make sure all your contributed and custom modules are ready. When you get a better understanding of composer, you'll realize what's going on. 

For me also, this is a warning that you should use as least contributed modules as possible and stick to core!

Use drupal check to test whether your modules are drupal 9 compatible. Still not working? Look at this screencast, it can help you with overcoming your last issues.