Should? No.
Why would you nofollow your own links to your own site?
If you don't want the tag pages indexed(different thing), that's your own choice and you can add the directive as a meta tag on the relevant page template, or you can just do it via robots.txt.
Do you have:
- a tag cloud somewhere on your site, like a page dedicated to it, or
- a giant cloud in a sidebar that appears everywhere on the site?
That post, and the Matt Cutts video, are mostly addressing the second case. If that's what you're doing, you really just need to reduce the size of the cloud.
For the first case, just noindex the page containing the cloud itself(as you'll see the StackExchange sites do). There's no reason to nofollow the actual links; the cloud being a massive block of text is the problem, not the links.