I think the animated gifs are a good beneficiary of flat design. If you have a limited number of colours, and you do not use gradients you don't need to use dithered patterns.
We are used to see this patterns becouse a lot of people use real video segments as avatars, etc. But in this case you have just some colours, lets say 20 and you have at your disposal 235 aditional colours to make the look smooth.
Here is the palete used on that particular gif.
I re-arranged the palete, so you can notice the more saturated colours, and the vast array of soft colours that make the aliased part of the shapes and the shadows.
The other thing is the high frame rate. That example has a frame rate of 375 frames in about 11-12 secs, that means that the framerate is like 30 fps, the same as a normal video.
To prepare a good palete:
The principles are the same regardless of the program you use.
1) Put all the elements you use in the entire animation in one canvas. Convert this canvas into 8 bit image, without any dithering, with an optimized or adaptive palete.
2) If you don't get a specific colour, for example a clean red for the little dot, make that shape bigger, so the program gives more importance to that part of the colour palete.
3) Extract that palete and force your original animation to use that controled palete.
Edited.
Probably the best program to do this kind of animation is After Effects, and Flash, which can export it directly to animated gif. (Other animation software can be used of course)
But I'm posting some free programs (win) than can achive simmilar results, but with some extra steps.
The animation
http://vectorian.com/ This is a free software for windows similar to flash. But as it only can save to swf file we need one aditional tool: http://www.pizzinini.net/projects/swf2avi/ And export a sequence of bmp files.
And, with the proper materials we can use http://www.blender.org/ to achive plain colors.
An intermediate step. Convert to video
You can use individual files to make an layered animation in gimp or photoshop. But you can automate the process by transforming them into a video if you have a lot of frames.
You can use http://www.virtualdub.org/
The conversion to gif
There is an abandonware that you probably can find Microsoft Gif Animator, verey usefull and can convert from avi to gif, with the option of aplying no dither.
But there are several free programs out there to convert from video to gif. I have not properly test them so I am not making any recomendation yet.
I will post some after some testing.
Photop Paint from Corel Can Process an avi file into animated gif directly.