For example, super strength, jedi-like abilities, etc? Or was he just really in tune with the spice melange? (Regarding the books, not the movies.)
Paul-Muad'Dib Atreides was the Kwisatz Haderach. None of his powers were supernatural - on the contrary, he was the desired (though early) result of a deliberate breeding programme - but they were certainly super-normal, which I believe to be a better term. The primary reason he was bred was to be "a male who would possess absolute prescience, seeing all possible futures and thus being able to cause select threads of time to be realized through manipulation." In other words, the Kwisatz Haderach could see all possible futures, and manipulate them to the advantage of the Bene Gessirit.
Paul-Muad'Dib, while being a Kwisatz Haderach, also had other abilities which were apparently unintended by-products of the breeding programme, as well as his unauthorised training by his mother and other Atreides household staff. He had the Bene Gesserit prana-bindu control over all of his muscles and nerves, which enabled him to do things like transform poisons into drinkable substances within his body (which is a skill possessed by some Jedi, such as Vergere and Jacen Solo, in the Star Wars EU, yes), and potentially granted him eternal youth; Paul didn't use his prana-bindu training for that, but his younger sister, Alia, did in Children of Dune. This did not protect her from physical violence. He was trained by Thufir Hawat as a Mentat, which essentially makes him a human computer. He was also trained in several eclectic fighting styles such as the Bene Gesserit "weirding way" (see the prana-bindu link above) of his mother and the Swordsmaster style of Gurney Halleck and Duncan Idaho.
In the David Lynch film, Paul is shown as possessing supernatural powers, such as the ability to control the weather; he makes it rain at the end of the film. In the introduction to Frank Herbert's anthology Eye, however, Herbert explicitly states that Paul was "a man pretending to be a god, not a god who could make it rain on Dune." I have that book sitting open in my lap as I type this, but if you want a reference you can read online, I can probably track it down for you. So Herbert himself believed that nothing Paul did was supernatural.
One could argue that the ability to see the future is supernatural, but isn't it really just an extension of Paul's latent Mentat abilities? The closest thing to a supernatural event in the books is when Paul drinks the Water of Life and somehow gains knowledge of Guild heighliners and Landsraad frigates orbiting Arrakis. This might also be a simple extension of his Mentat abilities; if the ships were in orbit, they presumably cast shadows, which a non-Mentat might not pick up on, while Paul's heightened state of awareness did. Or he could be sensing his ancestor, Baron Vladimir Harkonnen, nearby; Alia did this with Reverend Mother Gaius Mohiam in Dune.