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.