My slightly more recent experience was the same as the one described by Rafi and HaMagist. You need to be able to hike long distances in uniform and full gear, but you'll be trained to do that in tironut (basic training). You'll also be running short to long distances in shorts and sneakers and that's something you can and should train for at home.
There's also the physical fitness test which, though not very important at all if you plan on completing a more "standard" service like mine (being an enlisted man in a regular infantry unit), becomes more important if you plan on extending your service to become a sergeant or especially an officer later on, or if you want to try out for one of the special operations units within Nahal.
The basic physical fitness test consists of push-ups, (full) sit-ups, and a 2km run. The run counts for 70% of the score while the other two count for 15% each. To achieve a 100 you would need to run the 2km in 6:48 or less, do 75 or more push-ups (with no more than 2sec. between push-ups), and do 86 or more full sit-ups, fingers interlocked behind your head, feet on the ground, elbows touching your knees, with no more than 2 sec. between sit-ups.
The gibushim (try-outs) for the various special units in the Nahal and throughout the IDF vary in length, difficulty, and specific tasks. I didn't go to any gibush and, in any case, it's not for the raw draftee to know what's contained specifically in each one. What's important is that you have a great level of physical and mental endurance, and can hike on level ground or up hills while carrying heavy weight, can run long and short distances, can swim, and can perform well in various conditions even when the standard set for you is simply "do your best."
Mahal Nahal March '04 draft