I've given some thought to this, and I decided that I want to either make or find a theme to my fantasy novel before I really get into it (as I have started a couple pages already). I did some research online and found a whole lot of stuff about why stories should have theme and what theme is, but not much about how to make theme (Besides the usual "Oh, you'll figure it out eventually"). From what I can tell, this is kind of an unusual way to start out a book, so thanks for any advice :D
Something you need to be aware of when creating a theme before characters etc is that you can end up shoehorning characters into the theme they are telling.
If you're not careful with character development they can end up being stiffled by their 'role' in the general theme.
The benefit of ignoring theme until the story and characters are written is that the characters can 'be themselves' and develop naturally without needing a sudden backflip in order to make some significant thematic point.
The theme of a story is the message you want that story to convey.
In The Lord of the Rings (to use a fantasy example), the main theme is (IMO): "anyone can make a difference in the world, even if they are not someone one who wields obvious power". The main character is small and physically weak; despite this, thanks to Frodo's courage and the support of his friends, he defeats a powerful evil. (The theme is repeated in individual scenes for emphasis, like when Merry and Eowyn, a hobbit and a woman acting in the non-traditional gender role of a warrior, courageously defeat the Witch King, Sauron's most powerful lieutenant).
Would the same message have been conveyed if it were the great wizard Gandalf who carried the ring, or all-conquering Aragorn who had it in his pocket while slaying Orcs by the thousand? No. To make the point that Tolkien wanted to make, it was necessary for his hero to be helpless in battle, but prepared to do the right thing anyway - and if he'd started writing his story before knowing the theme, allowing it to "arise naturally", a really big rewrite might have been needed! It's even possible that after reading that book, people may even start to believe (consciously or unconsciously) that they, too, can make a difference, if only they are brave enough to do the right thing - even if they are not rich and powerful.
So, to directly answer your question: to decide on your theme, you need to decide the message you want your story to convey. (You could also think of it as the "moral of the story").
Let's assume your fantasy story is a classic battle-against-evil. You could just throw in some elves and some orcs, start writing, and hope you end up with a good story at the end. But perhaps you might decide that you want the theme to be "all that is necessary for evil to succeed is that good men do nothing". In that case, you might decide that the elves are choosing not to involve themselves in the affairs of orcs and humans, while the orcish army is rampaging through the realms of men. The hero in such a story might have a quest to find the elves in their hidden forest home, and convince them that after the cities of men have been burned to the ground, the woods of the elves will be next. This is just a quick idea off the top of my head, but doesn't it already sound more interesting than just throwing some elves and orcs into a fight? Doesn't it provide ideas for sub-plots and interesting scenes - like a man who decides not to get involved when he sees someone being attacked; but when he he is brought to understand the terrible consequences of that decision, he later bravely intervenes in a similar situation?
Theme drives both plot and character, and gives direction and purpose to the story. I don't claim for one moment that it's the only way to write a story, but a clearly defined theme helps you understand why you're writing the story in the first place, which in turn can tell you what and who needs to be in the story, and how the plot and sub-plots and individual scenes need to pan out. It all starts with deciding what you want your story to say. That's your theme.
(...and maybe, just maybe, as well as making the story more coherent and easier to write... it just might influence how your readers think, and how they behave. That's a difficult goal to achieve, but it can elevate a story from an entertaining but forgettable tale, to something truly profound and memorable.)
Your theme is the general statement you're making, but you can only make the statement via the plot. The plot should be developed via the organic actions of the characters.
Therefore, decide on your theme, figure out a rough plot which will express this theme, and staff the plot with characters who will accomplish it.
Just draw a map of the area and then write a description of each of the locations on the map. Write some little backstories of how each of the worlds factions came to be. Write descriptions of each of the cultures in your world and their history.
The benefit to doing this up front is that when you write the novel you can have characters casually drop references to historic events in an interesting way, rather than having to include big chunks of exposition whenever it becomes relevant. You can create the sense that the plot is just a side note in a world that is much bigger than the novels characters.
Try not to make your plot too big. ie: the plot should not be some epic jourmy to change the whole world. It should be more of a struggle just to change on small part of the world in one small way. And the charactor should start off as the opposite of what he needs to be in order to make that difference, so that he can go through changes himself. What ever these changes are that are necessary, that is the "Theme" as I understand the word.