Well, both actually. As long as you don't remove both starred provinces for a given resource type and per resource type remove exactly the number of territories according to player number indicated in the rulebook, you're free to pick them.
The removed territories are NOT random. At least that is how I understood the rules.
The last player (after play order has been determined at the start of the game) is given the ability to remove a certain number of territories from play.
The number of territories is equal to [one of each of the four types] time [number of players]. So in our game yesterday with three players, the last player was able to remove three gold, three wood, three marble, and three of the other one.
The restriction is that you cannot remove BOTH of the starred territories for any one type of resource.