From the 4e PHB, p 54:
Martial powers are not magic in the traditional sense, although some martial powers stand well beyond the capabilities of ordinary mortals. Martial characters use their own strength and willpower to vanquish their enemies. Training and dedication replace arcane formulas and prayers to grant fighters, rangers, rogues, and warlords, among others, their power.
That is to say, martial powers are not magic in the traditional sense - they are not like spells (arcane formulas) or prayers (divine magic). But nor are they "ordinary". Through strength and willpower, built up via training and dedication, martial PCs do extraordinary things that exceed the capabilities of mere mortals. REH's Conan is an example of a martial character in this sense. In LotR Boromir and Aragorn are both examples. It's clear within the fiction of LotR that neither is a wizard, nor using magic in the same way that Sauron does, or the user of a palantir does, or even the way that Feanor did to craft the Silmarils. Like Conan, each is drawing on his strength, willpower and dedication to do amazing things.