Having built a quite advanced GA based build order calculator myself, I can say that it involved a lot of analyzing the game, followed by recreating parts of the game engine that touch construction/advancement/worker movement.
I made a Tic-Tac-Toe GA in undergrad as my senior project. It was horribly stupid, but I didn't reduce the problem space down, and I could have easily implemented rotation and flip mapping to reduce the search space by a significant amount (just over 7% of the nieve search space), but the algorithm still worked pretty well and served as a great learning experience.
The genetic part is ridiculously simple, IMO. The hard part is figuring out how to define the rules of the game, break them out, and figure out what maps to the genome and how it maps. Evolution from that point is simply modifying the genome in different ways.
[1] http://wiki.teamliquid.net/starcraft2/Mining_Minerals
[2] http://www.teamliquid.net/forum/sc2-strategy/140055-scientif...