Well I can tell you what software I used:
For the actual painting of the map, I used Paint Shop Pro X, which is for sale in Media Markt for 9€.
For extracting a list of the province cultures from the scenario files I used the GNU Emacs text editor which is available for free on the web. (the files are very long so I deleted everything but the lines with "id = ..." and "culture = ...".).
For generating the maps for 1187, 1204 and 1337 I didn't actually go through the whole list of provinces again, instead I had a program compile me a list of differences between the 1066 data and the 1187 data, the program is WinDiff which is also for free on the web.
The template I used was made by Gratianus and is available here
http://forum.paradoxplaza.com/forum/showthread.php?t=215713.
The actual painting of the map was done by hand, using creatively some of the Paint Shop Tools such as multiple layers to create maps of the various scenarios (make layer 1 visible to see the 1066 map, then to see the 1187 map activate layer 2 which contains only the respective changes, and so on...) and the vector drawing feature which I used to set up auxillary layers such as the one which holds the province ID numbers. If you want I can send you my base file which contains all of that, it is in Paint Shop Pro format though (*.pspimage) so you'd have to invest 9€ to get PSP X.