[thejeff]

Doesn't seem to take province type into consideration.

What it seems to do:
When the order is given, choose the lowest numbered unsearched province.
When the spell is cast, again set the caster to cast the spell on the lowest numbered unsearched province, if the gems are available.
Two annoyances with this are, since spells are cast before battles, it will not target provinces taken that turn. Also, new gems haven't been acquired yet, so you have to have enough gems left at the end of the turn for next turn's searches.
I'm not sure what happens if a targetted province is taken. Probably the order is cancelled.