There are two flavors of evaluation function: If you can see the end of the game (as you always can with tic-tac-toe, even if you're running on a Commodore 64) you can base the result purely on whether the outcome is successful. The game engine will then only pick moves that win (or, if possible, tie).
If you can't see the endgame, which is by far more common in any interesting game, you need a function to score an intermediate board position in a way that measures how it favors each player. In Chess, for example, you might assign point values to each piece and add up how much material each side has and subtract. Thus the AI will favor ever greater material advantages. Then you give the evaluator bonus points for putting the opponent in check, and so on.
If you don't know much about how to play the game (I've written AIs for games I didn't know how to play more than once!) then you can simply tune your AI against humans or other AI players until it does well. I wrote a program specifically to play against the Microscope Puzzle in 7th Guest (it's a variation of Ataxx). I had to write it because my roommate and I couldn't beat the game! It was pretty clear that some function of board coverage was the right function, and I experimented with bonuses for connected groups and so on until my AI could beat the game's AI. I still can't beat Ataxx myself and my own AI is even more ruthless and slaughters me quickly.