Since the tagadelic module is not drupal 6 compatible yet,  you have to apply a patch:

wget http://drupal.org/files/issues/tagadelic-198672-16.patch

cvs -z6 -d:pserver:anonymous:anonymous@cvs.drupal.org:/cvs/drupal-contrib checkout -d tagadelic contributions/modules/tagadelic

cd tagadelic; patch -p0 < ../tagadelic-198672-16.patch

Now the module works in Drupal 6, but the content of your tagcloud is only updated when you run cron.php. I wanted to have this done automatically when I edited tags, when I add or remove content or changing the setting of the cloud. I found everything I needed to know here, but I will make it easy:

In modules/tagadelic/tagadelic.module change line 231:

from: cache_set($cache_name, $tags);

to: cache_set($cache_name, $tags, 'cache_page', CACHE_TEMPORARY);

As mentioned here, they will make it just a configuration option.

Loving Drupal each day more and more, and you have to love the ever growing community around it.