I read this post at Creative Cow which asked how to create the Commodore 64 look in Adobe After Effects. I got a bit inspired and tried it out a little, but for simplicity's sake I tried it on still images and used The GIMP instead.
Here are some results:
What I did was basically to convert the images to low resolution (160 pixels wide) with a 2:1 pixel aspect ratio (what the C64 had in the multicolour mode), then converted it to indexed colour using the original C64 palette (taken from the image on this page). Some manual tweaking of the levels before converting to indexed colour helped. Using more complex dithering gives better looking results, but in my opinion you lose a bit of the C64 look.
Sorry if the above description is short, but it's late. :-) So if you want to know more about how I did this, drop me a comment. It would be cool to try this with video too.