Adding (user-specified) tag support to WordPress

I have an old journal which is nearing its thousandth post. Things were rather old-school at the time I started it and it has grown somewhat organically, so I didn’t take the trouble to neatly classify my posts into categories.

As you can imagine, this makes sorting and searching through a few years worth of posts somewhat impossible. Since I am not too keen on going back and manually creating categories for (and categorising) every single post so far, I thought I’d be sneaky and pass the work onto my audience.

I am looking for something very similar to the tag functionality right here on this support forum, or (in pictures) how they’ve implemented it over at slashdot:

1. Every post lists popular user-specified tags.
2. User clicks that small triangle that brings up a form to add what they want.
3. They add their new tag or intensify what’s already there.
4. Once the number of repeats crosses a threshold, the tag joins the list of popular tags and shows up on the page.

All I need is a realistic estimation of:
1. How much support WordPress 2.x has “inherently” for tags. Either “inherently,” or through suitable, well thought out plug-ins?
2. How much work do you think it would be to pull off the implementation I describe using this support? Or if it already exists, where can I study/fetch it from?
3. How much work do you think it would be to incorporate this new information into WordPress’ search function, so it suitably uses it?

Thank you for your time. And if someone else is looking for something like this as well (and it doesn’t exist), we can collaborate on an implementation if you’re keen on it too.