Modernism, Surrealism, and possibly Parable, Dystopian Literature, or Tragedy
Kafka's a Modernist with a capital M. It has many of the themes of Modernism – whether you see it as an allegory of "modern bureaucracy," or totalitarianism, or a story of Tradition (the officer and the old Commandant) versus Modernity (the explorer), or a story about the decline of religion or a religious way of looking at the world.
It's also Modernist in the sense that it's experimental and non-traditional in style. There's the author's approach to sketching without details and leaving out many specifics (see "Writing Style" and "Setting"). The story's also not particularly plot-driven or character-driven, unlike more traditional literature. One particular object in the story – the apparatus – is described in great detail (taking up a large chunk of the narrative), whereas everything else, including the characters and the setting, is only sketched.
As for the other genre options, that depends on how you read the story. It's tempting to call it a parable, though it's a bit long for one, because Kafka was very fond of parables (he wrote two pieces he actually called by that name). In a way many of his works, excepting perhaps his novels, are like dysfunctional parables. As in parables, everything about the situation, plot, and characters is simplified or left merely sketched, so that all the attention is given to what the parable "means" or teaches. They're dysfunctional because what they mean is so irritatingly unclear!
You could also call "In the Penal Colony" a work of dystopian literature, especially if you look at it as an allegory for totalitarianism, because the kind of society the officer and the apparatus represent could be seen as a dystopia right up there with the world of 1984.
And you also could call the story a tragedy, if you view the officer as an admirable character. He would then be a kind of tragic hero, fated to go down because "Modernity" has rendered his world obsolete or because the kind of justice he wants is ultimately impossible (see "What's up with the Ending?," the plot analyses, and the officer's character analysis for more on this).