How does a large cargo plane like the C-130 Hercules take off and land in such a short distance?
Assault Takeoff/Landing Technique

This is a significant reason for the C-130's performance that you witnessed. "Assault" takeoff/landing speeds are lower than normal speeds, and closer to stall speed. Also there are some weight limitations. Further, the crew must be specifically trained. 

Stopping Quickly

Any idea of a smooth landing is thrown out the window. The intent is to "plant" the wheels at about 300 feet down the runway. That is, transition immediately from approach attitude to actually landing rather than assuming a touch-down attitude and letting the aircraft float down to the runway.

The nose gear is pushed to the ground and the instant the wheels are on the ground the props are thrown into full reverse, now pushing air forward. At the same time the pilot puts all his might into mashing the brakes. He would "stand on the brakes" as we say. The yoke is also pushed full forward which puts as much weight as possible on the landing gear. The anti-lock brake system is critical here, preventing skidding out of control and blown tires.

In Vietnam, in combat conditions, 130 pilots would put the props in reverse before touching down. If you've seen the video on YouTube of a C-130 landing on an aircraft carrier, they did it there too.

J's Props are a Huge factor

The performance boost of the J models thanks to the new prop and engine is amazing vis-a-vis the older models. But fundamental airframe limitations are still there. Nonetheless more blades (6 vice. 4) and the "un-ducted fan" design simply pushes more air.

Show Off Configuration

An empty airplane with a light fuel load of course maximizes the short takeoff and landing performance.

C-130 Has Fowler Flaps

Not blown flaps. Just because the props push air over the wing does not make it blown flaps. Otherwise, yes, the C-130 was given lots of flapage precisely for this purpose.