www.wayofthepixel.net/index.php?topic=15198.new#new did you happen to land this job by any chance? :p
to me it looks like he worked on this in photoshop with a 1px width aliased brush. I dont think you'll find a tutorial of how to make this unless the last designer wrote one.
I suggest you use 1px brushes and other small brushes with low opacity and try to pick colors with low saturation.
There was a guy who used to come here a very very long time ago, who made art similar to that but unfortunately I dont have a direct link to his site, and his name was always hard to pronounce.
His name was something like mahjiga, he made a big ben, animated some trains, a running cheetah, smoke effects all in photoshop with small brushes, like this style but better. He was very fond of making animated gif signatures. Any old timers here remember what was his actual name or have a link to his site?