Some of my blogs, a tag cloud is easier for visitors to find stuff than categories or search.
Other blogs, categories.
Other blogs, just search.
It really depends on your blog and your blog content as to whether go for tag clouds, categories and/or search.
Okay, here is one blog, it got a tag cloud built in because of someone posting in a thread of mine (either here or on namepros) asking me to make it easier than using the search function.
So now, when I post a new list of domains, I tag it.
And yes, it is used quite often, though not yet at the level the search function is used.