It depends on your preferred approach and patience.
Acid terrorist animates visuals frame by frame (from the stuff i've seen) in PETSCII (c64 native text mode with severe restrictions), which is utterly tedious, yet beautiful.
Another approach is to render your material to PETSCII/ASCII/ANSI automatically. You could check 'text mode demo compo' for more examples like this http://www.youtube.com/watch?v=TO4IyHZ0ci4.
Ofcourse there's a lot of inbetween solutions. If you don't care for it to run on a real C64 you have much more freedom. I'd personally go for 'ASCII-inspired' which could lead to new aesthetics, instead of following the path of e.g. Acid Terrorist.
I've done a couple of videos based on the C64, one inspired on the c64 palette and aesthetics, but neglecting the restrictions. (http://www.sanderfocus.nl/portfolio/comtron-money) Where i did static visuals in photoshop and animated these in 3d, After Effects or Flash.
The possibilites are endless, but i'd advice have a consistent approach, instead of merging all possible angles together.